#include <iostream>

using namespace std;

const int N = 100000;
struct node{
    int pre,k,next;
}nodes[N];
int head,n,k;

int main(){

    scanf("%d%d%d",&head,&n,&k);
    for(int i=0; i<n; i++){
        int add,k,ne;
        scanf("%d%d%d",&add,&k,&ne);
        nodes[add].k = k;
        nodes[add].next = ne;
    }
    int pr = -1,cnt=0;
    for(int i=head; i!=-1; i=nodes[i].next){
        nodes[i].pre = pr;
        pr = i;
        cnt ++;
    }
    //特殊判断一下  k<=1就不用翻转 直接输出就好
    if(k <= 1){
        for(int i=head; i!=-1; i=nodes[i].next){
            if(nodes[i].next != -1)
                printf("%05d %d %05d\n",i,nodes[i].k,nodes[i].next);
            else
                printf("%05d %d -1",i,nodes[i].k);
        }
        return 0;
    }

    int now=-1,nextgro=0;
    int rehead = -1;
    int temp = -1;
    //有些点不在链表中  所以是cnt/k  不是n/k
    for(int i=0; i<cnt/k; i++){    
        if(now == -1)
            now = head;
        else
            now = nextgro;

        //now先后走k-1个位置
        for(int j=0; j<k-1; j++){
            //cout <<"now = "<<now<<endl;
            now = nodes[now].next;
            nextgro = nodes[now].next;
        }
        if(rehead == -1) rehead = now;
        //从temp开始向前翻转链表
        if(temp != -1) nodes[temp].next = now;
        temp = now;
        for(int j=0; j<k-1; j++){
            nodes[temp].next = nodes[temp].pre; 
            temp = nodes[temp].pre;
        }
    }

    if(cnt%k !=0 ) nodes[temp].next = nextgro;
    else nodes[temp].next = -1;

    for(int j=rehead; j!=-1; j=nodes[j].next){
        if(nodes[j].next != -1)
            printf("%05d %d %05d\n",j,nodes[j].k,nodes[j].next);
        else
            printf("%05d %d -1",j,nodes[j].k);
    }

}