#include<bits/stdc++.h>
using namespace std;
typedef pair<int, int> PII;
const int N = 1e5 + 10;
int e[N],ne[N];
int main()
{
int n,k,head;
cin >> head >> n >> k;
for (int i = 0; i < n; i ++ ){
int a,b,c;
cin >> a >> b >> c;
e[a] = b;
ne[a] = c;
}
vector<PII> v;
for(int i = head ; i!=-1 ; i = ne[i]){
v.push_back({e[i],i});
}
n = v.size();
for(int i = 0 ; i < n ; i = i + k){
if(i + k <= n) reverse(v.begin()+i , v.begin()+i+k);
}
for(int i = 0; i < n; i ++)
if(i != n - 1) printf("%05d %d %05d\n", v[i].second, v[i].first, v[i + 1].second);
else printf("%05d %d -1\n", v[i].second, v[i].first);
}
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1e5 + 10;
int e[N],ne[N];
int main()
{
int head,n,k;
cin >> head >> n >> k;
for(int i = 0 ; i < n ; i++){
int a,b,c;
cin >> a >> b >> c;
e[a] = b;
ne[a] = c;
}
ne[N-1] = head;
head = N-1;
int i = ne[head],ne_head = ne[head],pre_tail = head;
int cnt = 0;
while(ne_head != -1)
{
cnt++;
ne_head = ne[ne_head];
if(cnt == k)
{
int pre = i,after = ne[i],start = i ;
while(after != ne_head)
{
pre = i;
i = after;
after = ne[i];
ne[i] = pre;
}
cnt = 0;
ne[start] = ne_head;
ne[pre_tail] = i;
pre_tail = start;
i = ne_head;
}
}
for (i = ne[head]; i != -1; i = ne[i])
{
printf("%05d %d ", i, e[i]);
if (ne[i] == -1) cout << -1;
else printf("%05d\n", ne[i]);
}
return 0;
}