#include<stdio.h>
#include<stdlib.h>
typedef struct{
    int data;
    int next;
}LQ[100005];      //把链表结点放入数组，利用数组的下标作为结点的地址
int flag[100005]; //由于题目是“去重”，所以，直接利用标签数组+下标来验证是否重复即可
int re[100005];   //这个数组放置的是去重完后的链表的结点的地址
int qu[100005];   //这个数组放置的是去重过程中，被去掉的结点的地址
int main(){
    LQ LL;
    int add,n;
    scanf("%d %d",&add,&n);
    int all = n;
    int n1 = 0,n2 = 0;
    while(n--){
        int x,y,z;
        scanf("%d %d %d",&x,&y,&z);
        LL[x].data = y;
        LL[x].next = z;
    }
    //读入完毕


    //从链表的首地址add开始，往后遍历链表，直到链表的结束(add = -1),每次让add 等于所指向的结点指向的下一个结点位置【下标】
    //通过判断标签数组中是否有该值，实现去重的功能
    //对于没有重复值的结点，将其地址i 存入 re数组
    //对于有重复值的结点，将其地址i 存入qu数组
    for(int i = add;i != -1;i = LL[i].next){
        int m = abs(LL[i].data);
        if(flag[m] == 0){
            flag[m] = 1;
            re[n1++] = i; //注意这里内部是 n1++
        }else{
            qu[n2++] = i;
        }
    }

    //打印去除结点的链表 --- re 数组
    for(int i = 0; i < n1;i++){
        if(i == n1 -1 )
            printf("%05d %d -1\n",re[i],LL[re[i]].data);
        else
            printf("%05d %d %05d\n",re[i],LL[re[i]].data,re[i+1]);
    }
    //可以看出来，re[n1++] ,qu[n2++] 的目的就是利用一个存放地址的数组的向后遍历实现链表结点间地址的“连续”
    //（通过 re[i+1] 访问下一个结点的地址）

    //同时，re，qu 里面存储了相应结点的地址，可以通过结构体数组LL快速访问该结点的值

    //打印被去掉的结点构成的链表 --- qu 数组
    for(int i = 0; i < n2;i++){
        if(i == n2 -1 )
            printf("%05d %d -1\n",qu[i],LL[qu[i]].data);
        else
            printf("%05d %d %05d\n",qu[i],LL[qu[i]].data,qu[i+1]);
    }
    return 0;
}