#include<bits/stdc++.h>

using namespace std;

const int N = 100010;

int h,e[N],ne[N];
int n,k;
int main()
{
    cin>>h>>n>>k;
    while(n--)
    {
        int address,data,next;
        cin>>address>>data>>next;
        e[address] = data;
        ne[address] = next;
    }
    vector<int> a,b;
    stack<int> s;
    for(int i = h; i!=-1; i = ne[i]) a.push_back(i);

    int cnt = 0;
    for(int i = 0; i< (int)a.size(); i+=k)
    {
        for(int j = 0; j<min(k,(int)a.size()-cnt*k); j++)
            b.push_back(a[i+j]);//a[0],a[1],a[2]
        for(int j = b.size()-1; j>=0; j--)
            s.push(b[j]);
        cnt++;
        b.clear();
    }
    while(s.size()!=1)
    {
        printf("%05d %d ",s.top(),e[s.top()]);
        s.pop();
        printf("%05d\n",s.top());
    }
    printf("%05d %d %d",s.top(),e[s.top()],-1);
    return 0;
}