#include <bits/stdc++.h>
using namespace std;

const int N = 100010;

struct
{
    int data, next;
} a[N];
int b[N], c[N];

int main()
{
    int p, n; cin >> p >> n;
    while (n--)
    {
        int pos; cin >> pos;
        cin >> a[pos].data >> a[pos].next;
    }

    int k1 = 0, k2 = 0;
    for (int i = p; i != -1; i = a[i].next) b[k1++] = i;

    int l = 0, r = k1 - 1;
    while (l <= r)
    {
        if (l == r) // 当结点为奇数个时
            c[k2++] = b[l++];
        else
        {
            c[k2++] = b[r--];
            c[k2++] = b[l++];
        }
    }
    for (int i = 0; i < k2; i++)
    {
        printf("%05d %d ", c[i], a[c[i]].data);
        if (i != k2 - 1) printf("%05d\n", c[i + 1]);
        else puts("-1");
    }
    return 0;
}