/*
# 问题分析
题设给定链表头节点地址, 总节点个数, 元素分类阈值, 要求按照指定的方式对链表元素进行分类排序。
指定方式为: 将元素的值按照"大于0", "大于等于0且小于等于给定阈值", "大于给定阈值"分为三组, 分组中的元素保持在原始链表中的相对顺序, 最后按照指定格式输出分类排序后的各个节点信息。
由于该题是通过输入校验, 所以如果在考试中, 为了追求更快获得正确解, 可以选择直接按照指定方式输出各个节点信息的方式。
比如: 将各个链表元素按照连接顺序放入连续的数组中, 然后给定规则对数组元素进行排序, 最后直接按照要求输出。
给定规则描述为: 两个元素处于同一取值区间时相对位置不变, 如果处于不同区间, 则按照数值大小递增排序。
 
# 完整描述步骤
1. 获取输入: 链表头节点, 节点个数, 区间阈值
2. 按照链表连接顺序, 将各个节点放入连续数组中, 并计算链表长度
3. 自定义排序规则:
    - 如果两个元素都小于0, 则两个元素顺序不变;
    - 如果两个元素都大于等于0且小于等于给定阈值, 则两个元素顺序不变;
    - 如果两个元素都大于给定阈值, 则两个元素顺序不变;
    - 否则, 按照元素值递增顺序排列两个元素;
4. 按照自定义规则对连续数组进行排序
5. 按照排序后的数组顺序输出各个节点的地址, 数据以及节点所在位置的下一个位置的元素的地址:
    - 如果是最后一个元素, 则输出"{该元素的地址} {数据} -1"
 
# 伪代码描述
1. get input: head, node_amount, threshold
2. put linked list into array, and calcualte length of array
3. define rule of array sorting:
    - if A < 0 and B < 0: not change order bewteen A and B;
    - if 0 <= A <= threshold and 0 <= B <= threshold: not change order bewteen A and B;
    - if A > threshold and B > threshold: not change order bewteen A and B;
    - else: sort A and B as value ascending
4. sorted array by defined sorting rule
5. for index in range(0, length(array)):
    - if index != length(array) - 1:
        - print("{array[i].address} {array[i].data} {array[i+1].address}");
    - else:
        - print("{array[i].address} {array[i].data} -1");
*/
 
# include<stdio.h>
 
typedef struct node{
    int address;
    int data;
    int next;
} node;
 
node nodes[100001];
int threshold;
 
 
int cmp(const void* a, const void* b){
    node node_a = *(node*)a;
    node node_b = *(node*)b;
    
    int A = node_a.data;
    int B = node_b.data;
    if (A < 0 && B < 0){
        return 0;
    }
    if (A > threshold && B > threshold){
        return 0;
    }
    if (0 <= A && A <= threshold && 0 <= B && B <= threshold){
        return 0;
    }
    
    return A > B;
}
 
 
int main(){
    int head, node_amount;
    scanf("%d %d %d", &head, &node_amount, &threshold);
    
    int address, data, next;
    for (int i = 0; i < node_amount; i++){
        scanf("%d %d %d", &address, &data, &next);
        nodes[address].address = address;
        nodes[address].data = data;
        nodes[address].next = next;
    }
    
    int valid_node_amount = 0;
    node valid_nodes[node_amount];
    int current_address = head;
    while (current_address != -1){
        valid_nodes[valid_node_amount] = nodes[current_address];
        valid_node_amount++;
        current_address = nodes[current_address].next;
    }
 
    qsort(valid_nodes, valid_node_amount, sizeof(node), cmp);
 
    for(int i = 0; i < valid_node_amount; i++){
        if (i == valid_node_amount-1){
            printf("%05d %d -1\n", valid_nodes[i].address, valid_nodes[i].data);
        } else {
            printf("%05d %d %05d\n", valid_nodes[i].address, valid_nodes[i].data, valid_nodes[i+1].address);
        }
    }
 
    return 0;
}