#include <bits/stdc++.h>

 using namespace std;

 const int inf=<<;

 typedef long long ll;

 typedef pair<int,int> P;

 const double pi=acos(-);

 const int mod=1e8+;

 const int maxn=1e5+;

 const int maxm=;

 struct node{

     int adress,val,next,num;

 }a[maxn];

 bool exist[maxn];

 int cnt,cnt1,cnt2;

 bool cmp(const node &a,const node &b){

     return a.num<b.num;

 }

 int main(){

     int begin,n;scanf("%d%d",&begin,&n);

     for(int i=;i<maxn;i++){

         a[i].num=*maxn;

     }

     for(int i=;i<n;i++){

         int x,y,z;scanf("%d",&x);

         a[x].adress=x;

         scanf("%d%d",&a[x].val,&a[x].next);

     }

     for(int i=begin;i!=-;i=a[i].next){

         if(!exist[abs(a[i].val)]){

             exist[abs(a[i].val)]=;

             a[i].num=cnt1;

             cnt1++;

         }

         else{

             a[i].num=cnt2+maxn;

             cnt2++;

         }

     }

     cnt=cnt1+cnt2;

     sort(a,a+maxn,cmp);

     for(int i=;i<cnt;i++){

         if(i==cnt1-||i==cnt-) printf("%05d %d -1\n",a[i].adress,a[i].val);

         else printf("%05d %d %05d\n",a[i].adress,a[i].val,a[i+].adress);

     }

     return ;

 }