#include <iostream>
#include <cstdio>
#include <cmath>
#include <unordered_set>

using namespace std;

// 定义链表节点的结构体，每个节点包含三个信息：自身地址、存储的键值、下一个节点的地址
struct Node {
    int addr;       // 节点的地址（5位整数）
    int data;       // 节点存储的键值（整数）
    int next;       // 下一个节点的地址（-1表示空）
} nodes[100000];   // 用数组存储所有节点，数组下标直接对应节点地址（因为地址是5位整数，最大99999）

int main() {
    int head, n;
    // 读取链表的头节点地址和节点总数n
    cin >> head >> n;

    // 读取n个节点的信息，并存入nodes数组中
    for (int i = 0; i < n; ++i) {
        int addr, data, next;
        cin >> addr >> data >> next;  // 读取当前节点的地址、键值、下一个节点地址
        nodes[addr] = {addr, data, next};  // 将节点信息存入数组对应位置（下标=地址）
    }

    // 创建一个哈希集合，用于记录已经出现过的键值的绝对值（快速判断是否重复）
    unordered_set<int> exist;
    // 定义去重后链表的头指针和尾指针（初始为-1表示空）
    int res_head = -1, res_tail = -1;
    // 定义被删除节点组成的链表的头指针和尾指针（初始为-1表示空）
    int del_head = -1, del_tail = -1;

    // 从链表头开始遍历整个原链表
    int current = head;  // current记录当前遍历到的节点地址
    while (current != -1) {  // 当current为-1时，链表遍历结束
        int val = nodes[current].data;  // 获取当前节点的键值
        int abs_val = abs(val);  // 计算键值的绝对值（用于判断重复）

        // 检查当前键值的绝对值是否在哈希集合中（即是否已出现过）
        if (exist.find(abs_val) == exist.end()) {
            // 未出现过：将当前节点加入去重后的链表

            exist.insert(abs_val);  // 把该绝对值存入集合，标记为已出现

            // 如果去重链表还是空的（头指针为-1），则当前节点成为头节点
            if (res_head == -1) {
                res_head = current;
                res_tail = current;  // 尾指针也指向当前节点（此时链表只有一个节点）
            } else {
                // 去重链表非空：将当前节点接在尾节点后面
                nodes[res_tail].next = current;  // 原尾节点的next指向当前节点
                res_tail = current;  // 更新尾指针为当前节点
            }
        } else {
            // 已出现过：将当前节点加入被删除的链表

            // 如果删除链表还是空的（头指针为-1），则当前节点成为删除链表的头节点
            if (del_head == -1) {
                del_head = current;
                del_tail = current;  // 尾指针也指向当前节点
            } else {
                // 删除链表非空：将当前节点接在删除链表的尾节点后面
                nodes[del_tail].next = current;  // 原删除链表尾节点的next指向当前节点
                del_tail = current;  // 更新删除链表的尾指针为当前节点
            }
        }

        // 移动到下一个节点：当前节点的next地址就是下一个节点的位置
        current = nodes[current].next;
    }

    // 处理两个链表的尾节点：将尾节点的next设为-1（表示链表结束）
    if (res_tail != -1) {  // 如果去重链表非空
        nodes[res_tail].next = -1;
    }
    if (del_tail != -1) {  // 如果删除链表非空
        nodes[del_tail].next = -1;
    }

    // 输出去重后的链表
    current = res_head;  // 从去重链表的头节点开始遍历
    while (current != -1) {
        // 如果当前节点是链表的最后一个（next为-1），按格式输出地址、键值、-1
        if (nodes[current].next == -1) {
            printf("%05d %d -1\n", nodes[current].addr, nodes[current].data);
        } else {
            // 非最后一个节点，输出地址、键值、下一个节点的地址（格式化为5位整数）
            printf("%05d %d %05d\n", nodes[current].addr, nodes[current].data, nodes[current].next);
        }
        current = nodes[current].next;  // 移动到下一个节点
    }

    // 输出被删除的链表（格式与去重链表相同）
    current = del_head;  // 从删除链表的头节点开始遍历
    while (current != -1) {
        if (nodes[current].next == -1) {
            printf("%05d %d -1\n", nodes[current].addr, nodes[current].data);
        } else {
            printf("%05d %d %05d\n", nodes[current].addr, nodes[current].data, nodes[current].next);
        }
        current = nodes[current].next;  // 移动到下一个节点
    }

    return 0;
}