#include<cstdio>

 #include<cstring>

 #include<cstring>

 #include<stack>

 #include<cmath>

 #define MAX_N 100000

 using namespace std;

 struct TYPE{

     int vul,next;

 };

 TYPE a[MAX_N+];

 int x[MAX_N+],y[MAX_N+];

 bool compare[MAX_N+];

 int main(void){

     //freopen("in.txt","r",stdin);

     int adress,n;

     scanf("%d%d",&adress,&n);

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

         int temp;

         scanf("%d",&temp);

         scanf("%d%d",&a[temp].vul,&a[temp].next);

     }

     int k1=,k2=;

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

         int temp=abs(a[i].vul);

         if(compare[temp]==false){

             x[k1++]=i;

             compare[temp]=true;

         }else{

             y[k2++]=i;

         }

     }

     printf("%05d %d ",x[],a[x[]].vul);

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

         printf("%05d\n",x[i]);

         printf("%05d %d ",x[i],a[x[i]].vul);

     }

     printf("-1\n");

     if(k2){

         printf("%05d %d ",y[],a[y[]].vul);

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

             printf("%05d\n",y[i]);

             printf("%05d %d ",y[i],a[y[i]].vul);

         }

         printf("-1\n");

     }

     return ;

 }