#include <bits/stdc++.h>
using namespace std;
const int maxn = 100010;

struct node
{
    int address;
    int data;
    int next;
}nodes[maxn];
int address1,n;
vector<node> V1;//存储全部
vector<node> V2;//存储有序
vector<node> V3;//存储被剔除
set<int> num;
int main()
{
    scanf("%d%d",&address1,&n);
    //获取数据
    for(int i=0;i<n;i++)
    {
        int temp_address;
        scanf("%d",&temp_address);
        nodes[temp_address].address = temp_address;
        scanf("%d %d",&nodes[temp_address].data,&nodes[temp_address].next);
    }
    
    //遍历一遍，过滤无效数据
    for(int s=address1;s!=-1;s=nodes[s].next)
    {
        V1.push_back(nodes[s]);
        num.insert(abs(nodes[s].data));
    }
    //最后
    for(int i=0;i<V1.size();i++)
    {
        if(num.find(abs(V1[i].data)) != num.end())
        {
            V2.push_back(V1[i]);
            num.erase(abs(V1[i].data));
        }
        else
        {
            V3.push_back(V1[i]);
        }
    }
    
    //输出有序
    for(int i=0;i<V2.size();i++)
    {
        if(i!=V2.size()-1)
            printf("%05d %d %05d\n",V2[i].address,V2[i].data,V2[i+1].address);
        else
            printf("%05d %d -1\n",V2[i].address,V2[i].data);
    }
    //输出被剔除的
    for(int i=0;i<V3.size();i++)
    {
        if(i!=V3.size()-1)
            printf("%05d %d %05d\n",V3[i].address,V3[i].data,V3[i+1].address);
        else
            printf("%05d %d -1\n",V3[i].address,V3[i].data);
    }
    return 0;
}