#include <iostream>
#include <cstring>
using namespace std;
const int N = 100010, M = 10010;
int e[N], ne[N], h1, h2=-1;
bool st[M];
int main(){
memset(ne, -1, sizeof ne);
int n, addr, x, next;
scanf("%d %d", &h1, &n);
for( int i=0; i<n; i++ ){
scanf("%d %d %d", &addr, &x, &next);
e[addr]=x, ne[addr]=next;
}
int t = e[h1];
if( t<0 ) t=-t;
st[t] = true;
int pre = h1; //pre表示p1所指向的结点前一个不重复的结点
int p1=ne[h1], p2=-1;
while( p1!=-1 ){
t = e[p1];
if( t<0 ) t=-t;
if( !st[t] ) st[t]=true, pre=ne[pre]; //结点不重复,pre可以向后移动
else{ //否则重复结点加到链表2中
if( p2==-1 ) p2=p1, h2=p1; //表头
else ne[p2] = p1, p2=ne[p2];
ne[pre] = ne[p1]; //pre的下一个指向p1的下一个
}
p1 = ne[p1];
}
ne[p2] = -1; //最后把链表2的尾巴设为-1
p1 = h1, p2 = h2;
while( p1!=-1 ){//地址5位数
printf("%05d %d ", p1, e[p1]);
p1 = ne[p1];
if( p1==-1 ) puts("-1");
else printf("%05d\n", p1);
}
while( p2!=-1 ){//地址5位数
printf("%05d %d ", p2, e[p2]);
p2 = ne[p2];
if( p2==-1 ) puts("-1");
else printf("%05d\n", p2);
}
return 0;
}