#include<iostream>
#include<algorithm>
#include<unordered_map>

using namespace std;

unordered_map<int ,int > map;
const int N=100009;
int nex[N],v[N];

int start,n;

int main()
{
    cin>>start>>n;
    for(int i=0;i<n;i++)
    {
        int a,b,c;

        cin>>a>>b>>c;
        if(c==-1) c=100006;
        nex[a]=c;
        v[a]=b;

    }

    vector<pair<int,int>> res;
    vector<pair<int,int>> lost;

    while(start!=100006)
    {
        if(map[abs(v[start])]==0)
        {
            map[abs(v[start])]=1;
            res.push_back({v[start],start});


        }
        else
        lost.push_back({v[start],start});


        start=nex[start];

    }


    for(int i=0;i<res.size();i++)
     {
         if(i==res.size()-1)

     printf("%05d %d -1 \n",res[i].second,res[i].first);
         else

        printf("%05d %d %05d \n",res[i].second,res[i].first,res[i+1].second);
     }    
     for(int i=0;i<lost.size();i++)
     {
         if(i==lost.size()-1)

          printf("%05d %d -1 \n",lost[i].second,lost[i].first);
         else

          printf("%05d %d %05d \n",lost[i].second,lost[i].first,lost[i+1].second);

     }

    return 0;

}