//constant常数 singly linked list单链表
//the length of the sublist子列表的长度
//5-digit nonnegative intege5位非负整数
#include<iostream>
#include<algorithm>
#include<cstring>
#include<vector>

using namespace std;

const int N = 100010;

int n,k;
int h,e[N],ne[N];

int main()
{
    cin>>h>>n>>k;
    for(int i = 0; i<n; i++)
    {
        int address,data,next;
        cin>>address>>data>>next;
        e[address] = data,ne[address] = next;
    }
    vector<int> q;
    for(int i = h; i!=-1; i = ne[i]) q.push_back(i);

    for(int i = 0; i+k-1<q.size(); i+=k)
        reverse(q.begin()+i,q.begin()+i+k);
    for(int i = 0; i<q.size(); i++)
    {
        printf("%05d %d ",q[i],e[q[i]]);
        if(i+1 == q.size()) puts("-1");
        else printf("%05d\n",q[i+1]);//下一个点的地址
    }
    return 0;
}