#include <iostream>
#include <unordered_set>

using namespace std;

unordered_set<int> has;
const int N = 100000;
typedef struct node{
    int key;
    int next;
}node;
//keepnodes保存没被删除的节点  delnodes保存要删的节点
node nodes[N],keepnodes[N],delnodes[N];
int n,head,keephead=-1,keepidx=-1,delhead=-1,delidx=-1,keepcnt,delcnt;

int main(){
    scanf("%d %d",&head,&n);
    int pr = -1;
    while(n --){
        int p,k,np;
        scanf("%d %d %d",&p,&k,&np);
        nodes[p].key = k;
        nodes[p].next = np;
    }

    for(int i=head; i!=-1; i = nodes[i].next){
        int k = abs(nodes[i].key);
        if(has.find(k) == has.end()){
            has.insert(k);
            //
            if(keephead == -1){
                keephead = i;
                keepnodes[i].key = nodes[i].key;
                keepnodes[i].next = -1;
                keepidx = i;
            }else{
                keepnodes[keepidx].next = i;
                keepidx = i;
                keepnodes[keepidx].next = -1;
                keepnodes[i].key = nodes[i].key;
            }
            keepcnt ++;
        }
        else{
            if(delhead == -1){
                delhead = i;
                delnodes[i].key = nodes[i].key;
                delnodes[i].next = -1;
                delidx = i;
            }else{
                delnodes[delidx].next = i;
                delidx = i;
                delnodes[delidx].next = -1;
                delnodes[i].key = nodes[i].key;
            }
            delcnt ++;
        }
    }
    for(int i=keephead; i!=-1; i=keepnodes[i].next)
        if(keepnodes[i].next != -1)
            printf("%05d %d %05d\n",i,keepnodes[i].key,keepnodes[i].next);
        else
            printf("%05d %d -1\n",i,keepnodes[i].key);

    for(int i=delhead; i!=-1; i=delnodes[i].next)
        if(delnodes[i].next != -1)
            printf("%05d %d %05d\n",i,delnodes[i].key,delnodes[i].next);
        else
            printf("%05d %d -1\n",i,delnodes[i].key);

}