#include <cstdio>
#include <cmath>
#include <vector>
using namespace std;
const int maxn = 100010;
struct Node{int address, data, next, flag;Node(){flag = 0;}
}nodes[maxn];
int ma[10001];
int del(int pre, int cur){int next = nodes[cur].next;nodes[pre].next = next;return next;
}
int main() {int head,n;scanf("%d%d", &head, &n);int add;for(int i = 0; i < n; i++){scanf("%d", &add);scanf("%d%d", &nodes[add].data, &nodes[add].next);nodes[add].address = add;}ma[abs(nodes[head].data)] = 1;int pre=head,cur=nodes[head].next,d;vector<int> delNodes;while(cur != -1){int d = abs(nodes[cur].data);if(ma[d] == 1){delNodes.push_back(cur);cur = del(pre,cur);}else{ma[abs(nodes[cur].data)] = 1;pre = cur;cur = nodes[cur].next;}}int p;for(p = head; p != -1; p = nodes[p].next){if(nodes[p].next != -1){printf("%05d %d %05d\n", nodes[p].address, nodes[p].data, nodes[p].next);}else{printf("%05d %d -1\n", nodes[p].address, nodes[p].data);}}for(int i = 0; i < delNodes.size(); i++){if(i < delNodes.size()-1){printf("%05d %d %05d\n", nodes[delNodes[i]].address, nodes[delNodes[i]].data, nodes[delNodes[i+1]].address);}else{printf("%05d %d -1\n", nodes[delNodes[i]].address, nodes[delNodes[i]].data);}}return 0;
}