#include <iostream>
#include <cstring>
using namespace std;

const int N = 100010;
int e[N], ne[N], h, n, k;
int link[N], idx;

void reverse(int p){
    while( p!=-1 ){
        link[idx++] = p;
        p = ne[p];
    }//存下地址

    int t = (idx-1) / k; 　//共有多少块，从０开始
    h = link[t*k];　    　//修改头结点为最后一块的第一个结点
    int tail = idx - 1;   //最后一块的最后一个结点
    for( int i=t-1; i>=0; i-- ){
        int j = i * k + k - 1;　　    //第i块的最后一个结点
        ne[link[j]] = ne[link[tail]]; //第i块的最后一个结点指向上一块最后一个结点的next
        ne[link[tail]] = link[i*k];   //上一块最后一个结点指向第i块的第一个结点
        tail = j;                     //记下第 i 块的最后一个结点
    }
}

int main(){
    scanf("%05d %d %d", &h, &n, &k);
    int addr, val, next;
    while( n-- ){
        scanf("%05d %d %05d", &addr, &val, &next);
        e[addr]=val, ne[addr]=next;
    }
    reverse(h);
    int p = h;
    while( p!=-1 ){
        printf("%05d %d ", p, e[p]);
        if( ne[p]!=-1 ) printf("%05d\n", ne[p]);
        else puts("-1");
        p = ne[p];
    }
    return 0;
}