#include <iostream>
#include <cstdio>
#include <algorithm>
#include <string.h>
#include <cmath>
using namespace std;

const int maxn=100000+5;
struct Node{
    int addr;
    int value;
    int to;
}node[maxn];
int flag[maxn];
int linkedlist[maxn];  //去重后的链表
int removelist[maxn];  //删除节点组成的链表

int main()
{
    int head,n;
    int a,b,c;
    for(int i=0;i<maxn;i++)
        flag[i]=-1;
    ///memset(flag,0,sizeof(flag)); 地址中存在为0的情况，所以不能用0表示还没出现啊啊
    scanf("%d %d",&head,&n);
    for(int i=0;i<n;i++){
        scanf("%d %d %d",&a,&b,&c);
        node[a].addr=a;
        node[a].value=b;
        node[a].to=c;
    }
    int tmp;
    int cnt1=0,cnt2=0;
    int lastaddr=-1; //存储目前linkedlist链表的最后一个节点
    do{
        tmp=abs(node[head].value);
        if(flag[tmp]==-1){
            linkedlist[cnt1++]=node[head].addr;
            flag[tmp]=node[head].addr;
            lastaddr=head;
        }
        else{
            removelist[cnt2++]=node[head].addr;
            node[lastaddr].to=node[head].to;
        }
        head=node[head].to;
    }while(head!=-1);

    int id;
    //更新removelist中节点的to
    for(int i=0;i<cnt2-1;i++){
        id=removelist[i];
        node[id].to=node[removelist[i+1]].addr;
    }
    node[removelist[cnt2-1]].to=-1;
    node[linkedlist[cnt1-1]].to=-1;
    for(int i=0;i<cnt1-1;i++){
        id=linkedlist[i];
        printf("%05d %d %05d\n",node[id].addr,node[id].value,node[id].to);
    }
    //注意最后因为地址是-1，所以得另外输出
    if(cnt1>=1){
        id=linkedlist[cnt1-1];
        printf("%05d %d %d\n",node[id].addr,node[id].value,node[id].to);
    }
    for(int i=0;i<cnt2-1;i++){
        id=removelist[i];
        printf("%05d %d %05d\n",node[id].addr,node[id].value,node[id].to);
    }
    if(cnt2>=1){
        id=removelist[cnt2-1];
        printf("%05d %d %d\n",node[id].addr,node[id].value,node[id].to);
    }
    return 0;
}