#include<iostream>
#include<cmath>
#include<set>
#include<vector>
#define maxn 1000005

using namespace std;

struct Node{
   
	int address,data,next;
}node[maxn];

int main(){
   
	int head,n,address,data,next;
	scanf("%d%d",&head,&n);
	for(int i=0;i<n;i++){
   
		scanf("%d%d%d",&address,&data,&next);
		node[address]={
   address,data,next};
	}
	vector<Node> result,removed;
	set<int> occured;
	for(int p=head;p!=-1;p=node[p].next){
   
		if(occured.find(abs(node[p].data))!=occured.end())
		removed.push_back(node[p]);
		else{
   
			occured.insert(abs(node[p].data));
			result.push_back(node[p]);
		}
	}
	for(int i=1;i<result.size();i++)
		printf("%05d %d %05d\n",result[i-1].address,result[i-1].data,result[i].address);
		if(result.size()>0)
		printf("%05d %d -1\n",result[result.size()-1].address,result[result.size()-1].data);

	for(int i=1;i<removed.size();i++)
		printf("%05d %d %05d\n", removed[i-1].address, removed[i-1].data, removed[i].address);
		if (removed.size() > 0) printf("%05d %d -1\n", removed[removed.size()-1].address, removed[removed.size()-1].data);

}