/*
題意：給一個鏈表锣尉，然后給出一個K刻炒，每K個節(jié)點反轉(zhuǎn)一次

解題：
1、定義及靜態(tài)鏈表自沧，order表示在鏈表中的序號坟奥，
2、初始化拇厢，令order的初值均為maxn爱谁，表示初始時所有節(jié)點為無效節(jié)點
3、由題目給出的鏈表首地址begi遍歷整條鏈表孝偎，并記錄每個有效節(jié)點在鏈表中的序號访敌，統(tǒng)計技術(shù)有效節(jié)點的個數(shù)count。
4衣盾、對節(jié)點進行排序寺旺，按節(jié)點order從小到大排序
5爷抓、輸出鏈表，這個很煩
將n個節(jié)點分塊n/k塊阻塑，枚舉這些完整的塊蓝撇，從后往前輸出節(jié)點信息、注意每一個塊最后節(jié)點next的處理
（1）如果i號塊不是最后一個完整快叮姑，那么next就是（i+2)*k - 1號節(jié)點，也就是（i+1)號塊最后一個節(jié)點
（2）如果i號塊是最后一個塊据悔，同樣有兩種情況
一传透、如果n%k==0，則說明這是整個單聊表的最后一個節(jié)點极颓，輸出-1
二朱盐、如果n%k不等于0，則說明這個完整快后面還有一點尾巴菠隆，那么這個完整塊的最后一個節(jié)點的next不是下一個塊的最后一個兵琳，而是這個塊的第一個，接下來骇径，從前往后輸出即可

learn && wrong:
1躯肌、存在無效節(jié)點的可能
2、反轉(zhuǎn)鏈表只改變節(jié)點的next地址破衔，不改變本身地址清女，因此address和data是綁定的
3、%05d的輸出格式會讓-1出現(xiàn)錯誤晰筛，所以-1要單獨輸出
4嫡丙、給order排序很好
5、排序后輸出下一個節(jié)點读第，就是【i+1】.adderss就很不錯
*/

#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
const int maxn = 100010;

struct Node{    //定義鏈表曙博，步驟1
    int address,data,next;
    int order;  //節(jié)點在鏈表上的序號，無效節(jié)點為maxn
}node[maxn];

bool cmp(Node a,Node b){
    return a.order < b.order;   //按order從小到大排序
}

int main()
{
    for(int i = 0;i <maxn;i++){ //初始化（步驟2）
        node[i].order = maxn;   //  初始化全部為無效節(jié)點
    }

    int begin, n, K, address;
    scanf("%d%d%d", &begin, &n, &K);    //起始地址怜瞒，節(jié)點個數(shù)父泳、步長
    for(int i = 0;i < n;i++){
        scanf("%d",&address);
        scanf("%d%d", &node[address].data, &node[address].next);
        node[address].address = address;
    }

    int p = begin, count = 0;   //count計數(shù)有效節(jié)點的數(shù)目

    while(p != -1){ //遍歷鏈表找出單鏈表的所有效節(jié)點（步驟3）
        node[p].order = count++;    //節(jié)點在單鏈表中的序號
        p = node[p].next;  //下一個結(jié)點
    }

    sort(node, node + maxn, cmp);   //按單鏈表從頭到尾順序排列（步驟4）
    //有效節(jié)點為前count個節(jié)點，為了下面書寫方便吴汪，因此把count賦給n
    n = count;
    //單鏈表已經(jīng)形成尘吗，下面是按題目要求的輸出（步驟5）
    for(int i = 0;i < n / K;i++){   //枚舉完整的n / K 塊
        for(int j = (i + 1) * K - 1;j < i * K;j--){ //第i塊倒著輸出
            printf("%05d %d %05d\n",    node[j].address, node[j].data, node[j - 1].address);
        }

        //下面是每一塊的最后一個結(jié)點的next地址的處理
        printf("%05d %d ", node[i * K].address, node[i * K].data);
        if(i < n / K - 1){  //如果不是最后一塊，就指向下一塊的最后一個結(jié)點
            printf("%05d\n", node[(i+2) * K - 1].address);
        }else{  //是最后一塊時
            if(n % K == 0){ //恰好是最后一個結(jié)點浇坐，輸出-1
                printf("-1\n");
            }else{  //剩下的不完整塊按原先的順序輸出
                printf("%05d\n", node[(i + 1) * K].address);
                for(int i = n / K * K;i < n;i++){
                    printf("%05d %d", node[i].address, node[i].data);
                    if(n < -1){
                        printf("%05d\n",node[i+1].address);
                    }else{
                        printf("-1\n");
                    }
                }
            }
        }
    }
    return 0;
}