/*
# 问题分析
题设给定链表头节点地址, 总节点个数, 区块大小, 要求按照指定方式以区块为单位, 反转链表中的区块顺序。
指定方式为: 按照给定区块大小将链表划分为不同区块, 然后将区块逆序, 区块内元素相对顺序不变。
由于该题是通过输入校验, 所以如果在考试中, 为了追求更快获得正确解, 可以选择直接按照指定方式输出各个节点信息的方式。
比如: 将各个链表元素按照连接顺序放入连续的数组中, 然后按照给定长度划分区块, 最后直接从最后一个区块往第一个区块的顺序，按照要求输出。
 
# 完整步骤描述
1. 获取输入: 链表头节点地址, 总节点个数, 区块大小
2. 按照链表连接顺序, 将各个节点放入连续数组中, 并计算链表长度
3. 按照指定区块长度划分排列的数组, 从最后一个区块开始, 第一个区块结束:
    - 输出各个节点的地址, 数据以及节点所在位置的下一个位置的元素的地址:
    - 如果当前元素是原链表第一个元素, 则输出"{该元素的地址} {数据} -1"
 
# 伪代码描述
1. get input: head, node_amount, group_size
2. put linked list into array, and calcualte length of array
3. calculate group_amount = length(array) / group_size;
4. init new empty array
5. if length(array) > group_size * group_amount:
    - for nodex_index in range(group_size * group_amount, length(array)):
        - new_array.append(array[nodex_index])
6. for group_index in range(0, group_amount):
    - for nodex_index in range(group_size * group_index, group_size * (group_index+1)):
        - new_array.append(array[nodex_index])
7. for index in range(0, length(array)):
    - if index != length(array) - 1:
        - print("{new_array[i].address} {new_array[i].data} {new_array[i+1].address}");
    - else:
        - print("{array[i].address} {array[i].data} -1");
*/
 
# include<stdio.h>
 
typedef struct {
    int address;
    int data;
    int next;
} node;
 
node nodes[100000];
 
int main(){
    int head, node_amount, group_size;
    scanf("%d %d %d", &head, &node_amount, &group_size);
 
    int address;
    for (int i = 0; i < node_amount; i++){
        scanf("%d ", &address);
        scanf("%d %d", &nodes[address].data, &nodes[address].next);
        nodes[address].address = address;
    }
    
    int addresses[node_amount];
    int data[node_amount];
    int valid_amount = 0;
    int current_address = head;
    while (current_address != -1){
        addresses[valid_amount] = nodes[current_address].address;
        data[valid_amount] = nodes[current_address].data;
        current_address = nodes[current_address].next;
        valid_amount++;
    }
 
    int reversed_blocks_address[valid_amount];
    int reversed_blocks_data[valid_amount];
    int node_index = 0;
    int group_amount = valid_amount / group_size;
    if (valid_amount > group_size * group_amount){
        for (int i = group_amount * group_size; i < valid_amount; i++){
            reversed_blocks_address[node_index] = addresses[i];
            reversed_blocks_data[node_index] = data[i];
            node_index++;
        }
    }
 
    for (int i = group_amount - 1; i >= 0; i--){
        for (int j = 0; j < group_size; j++){
            reversed_blocks_address[node_index] = addresses[i*group_size+j];
            reversed_blocks_data[node_index] = data[i*group_size+j];
            node_index++;
        }
    }
    
    for (int i = 0; i < valid_amount; i++){
        if (i + 1 == valid_amount){
            printf("%05d %d -1\n", reversed_blocks_address[i], reversed_blocks_data[i]);
        } else {
            printf("%05d %d %05d\n", reversed_blocks_address[i], reversed_blocks_data[i], reversed_blocks_address[i+1]);
        }
    }
    
    return 0;
}