#include <iostream>
#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#include <memory.h>
/*
思路:将输入存放进数组，只要拿到去重后链表的头结点，和被删除链表的头结点，利用我们首先建立好的数组，就可以实现目标的输出
2017.8.13
作者：世界上最伟大最牛逼最屌的程序员
地点：西农
*/
using namespace std;
struct node
{
    int data, next;
} list1[100000];
int main()
{
    int key[10000];
    memset(key, 0, sizeof(key));
    int beforeRemoveDuplicates[100000];  //record the address of linked list after move duplicates
    int Duplicates[100000];   //record the address of linked list  duplicates
    int firstAddress, nodeNumber;
    cin >> firstAddress >> nodeNumber;
    int a, b, c;   //三个变量，输入用
    for(int i=0; i<nodeNumber; i++)
    {
        cin >> a >> b >> c;
        list1[a].data = b;
        list1[a].next = c;
    }
    int temp = firstAddress, t, i=0, j=0;  //travel a number array as a temporary variable
    while(temp!=-1)
    {
        t = abs(list1[temp].data);
        if(key[t]==0)
        {
            key[t]=1;
            beforeRemoveDuplicates[i++] = temp;
        }
        else
        {
            Duplicates[j++] = temp;
        }
        temp = list1[temp].next;
    }
    printf("%05d %d", beforeRemoveDuplicates[0], list1[beforeRemoveDuplicates[0]].data);
    for(int k=1; k<i; k++)
    {
        printf(" %05d", beforeRemoveDuplicates[k]);
        printf("\n%05d %d", beforeRemoveDuplicates[k], list1[beforeRemoveDuplicates[k]].data);
    }
    cout << " -1" << endl;
    if(j!=0)
    {
        printf("%05d %d", Duplicates[0], list1[Duplicates[0]].data);
        for(int k=1; k<j; k++)
        {
            printf(" %05d", Duplicates[k]);
            printf("\n%05d %d", Duplicates[k], list1[Duplicates[k]].data);
        }
        cout << " -1" << endl;
    }
    //cout << "Hello world!" << endl;
    return 0;
}