#include<algorithm>
#include <iostream>
#include  <cstdlib>
#include  <cstring>
#include   <string>
#include   <vector>
#include   <cstdio>
#include    <queue>
#include    <stack>
#include    <ctime>
#include    <cmath>
#include      <map>
#include      <set>
#define INF 0xffffffff
#define db1(x) cout<<#x<<"="<<(x)<<endl
#define db2(x,y) cout<<#x<<"="<<(x)<<", "<<#y<<"="<<(y)<<endl
#define db3(x,y,z) cout<<#x<<"="<<(x)<<", "<<#y<<"="<<(y)<<", "<<#z<<"="<<(z)<<endl
#define db4(x,y,z,r) cout<<#x<<"="<<(x)<<", "<<#y<<"="<<(y)<<", "<<#z<<"="<<(z)<<", "<<#r<<"="<<(r)<<endl
using namespace std;

typedef struct node
{
    int id,val,next;
}node;
node num[100005],news[100005],del[100005];

int main(void)
{
    #ifdef test
    freopen("in.txt","r",stdin);
    //freopen("in.txt","w",stdout);
    clock_t start=clock();
    #endif //test

    int root,m;scanf("%d%d",&root,&m);
    int cnt[100005]={0};
    for(int i=0;i<m;++i)
    {
        int id,val,next;scanf("%d%d%d",&id,&val,&next);
        num[id].id=id,num[id].val=val,num[id].next=next;
    }
    int ends=num[root].next,ln=1,ld=0;
    news[0]=num[root];
    int sum=num[root].val;
    if(sum<0)sum*=-1;
    cnt[sum]=1;
    while(ends!=-1)
    {
        int temp=num[ends].val;
        if(temp<0)temp=temp*-1;
        if(cnt[temp]==0)news[ln++]=num[ends],cnt[temp]++;
        else del[ld++]=num[ends];
        ends=num[ends].next;
    }
    for(int i=0;i<ln;++i)
    {
        printf("%05d %d ",news[i].id,news[i].val);
        if(i+1<ln)printf("%05d\n",news[i+1].id);
        else printf("-1\n");
    }
    for(int i=0;i<ld;++i)
    {
        printf("%05d %d ",del[i].id,del[i].val);
        if(i+1<ld)printf("%05d\n",del[i+1].id);
        else printf("-1\n");
    }

    #ifdef test
    clockid_t end=clock();
    double endtime=(double)(end-start)/CLOCKS_PER_SEC;
    printf("\n\n\n\n\n");
    cout<<"Total time:"<<endtime<<"s"<<endl;        //s为单位
    cout<<"Total time:"<<endtime*1000<<"ms"<<endl;    //ms为单位
    #endif //test
    return 0;
}