板子题， 考察链表知识， 直接模拟即可。

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define _for(i, a, b) for(int i = a; i < b; i++)
#define _rep(i, a, b) for(int i = a; i <= b; i++)
using namespace std;

const int MAXN = 1e5 + 10;

int h, e[MAXN], n0[MAXN], n;
bool st[MAXN];

int main() {
    cin >> h >> n;
    int a, b, c;
    _for(i, 0, n) {
        cin >> a >> b >> c;
        e[a] = b , n0[a] = c;
    }
    int a1[MAXN], e1[MAXN];
    int post = MAXN - 5,idx = h, cnt1 = n, cnt2 = 0;
    _for(i, 0, n) { 
        int j = e[idx];
        if(!st[abs(j)]) {
            st[abs(j)] = true;
            post = idx;
        } else {
            e1[cnt2] = e[idx], a1[cnt2] = idx;
            n0[post] = n0[idx];
            cnt1--, cnt2++;
        }
        idx = n0[idx];
    }
    idx = h;
    _for(i, 0, cnt1) {
        if(n0[idx] != -1) printf("%05d %d %05d\n", idx, e[idx], n0[idx]);
        else printf("%05d %d -1\n", idx, e[idx]);
        idx = n0[idx];
    }
    _for(i, 0, cnt2) {
        if(i != cnt2 - 1) printf("%05d %d %05d\n", a1[i], e1[i], a1[i + 1]);
        else printf("%05d %d -1\n", a1[i], e1[i]);
    }
    return 0;
}