#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
struct node
{
int key,next;
}orignal[N];
struct ans
{
int address,key,next;
}result[N],removed[N];//orignal表示原先的链表,result表示结果的链表,removed表示删除的链表
bool st[N];//记录节点是否已经被访问过
int main()
{
int start,n;//start表示起始的节点,n表示节点的数量
scanf("%d%d",&start,&n);
for(int i=0;i<n;i++)
{
int address,key,next;
scanf("%d%d%d",&address,&key,&next);
orignal[address]={key,next};
}
int res_cnt=0;
int rem_cnt=0;
for(int i=start;i!=-1;i=orignal[i].next)
{
if(st[abs(orignal[i].key)]==false)//表示当前节点还没有存入过result,那么说明这个节点还是新鲜的
{
st[abs(orignal[i].key)]=true;//表示这个节点我已经访问过了,后面的点就不要去访问了
if(res_cnt==0)//表示我是第一次存入result中,那么我就需要标记一下起始点
result[res_cnt++]={i,orignal[i].key,-1};//将这个节点存入到remove中,并将下一个节点的坐标指向-1,因为我们在这里还不知道他下一个节点要只向谁
else
{
result[res_cnt-1].next=i;//前一个点的下一个指针指向当前的地址
result[res_cnt++]={i,orignal[i].key,-1};//将这个节点存入到result中
}
}
else//如果这个节点已经存入过result中,那么我就不需要继续存了,将其存入到result中
{
if(rem_cnt==0)//表示我是第一次存入result中,那么我就需要标记一下起始点
removed[rem_cnt++]={i,orignal[i].key,-1};//将这个节点存入到remove中,并将下一个节点的坐标指向-1,因为我们在这里还不知道他下一个节点要只向谁
else
{
removed[rem_cnt-1].next=i;//前一个点的下一个指针指向当前的地址
removed[rem_cnt++]={i,orignal[i].key,-1};//将这个节点存入到remove中
}
}
}
for(int i=0;i<res_cnt;i++)
{
printf("%05d %d ",result[i].address,result[i].key);
if(result[i].next==-1)printf("-1\n");
else printf("%05d\n",result[i].next);
}
for(int i=0;i<rem_cnt;i++)
{
printf("%05d %d ",removed[i].address,removed[i].key);
if(removed[i].next==-1)printf("-1\n");
else printf("%05d\n",removed[i].next);
}
return 0;
}