#include <cstdio>

 #include <cstdlib>

 #include <iostream>

 #include <unordered_map>

 using namespace std;

 class Node {

 public:

     int data;

     int next;

     Node() : data(), next() {}

     Node(int d, int n):data(d), next(n){}

 };

 int reverse_help(int head, int k, unordered_map<int, Node>& mem) {

     if (head == -) {

         return -;

     }

     int cur = head;

     int prev= -;

     while (cur != -) {

         if (k == ) {

              break;

         }

         int tmp = mem[cur].next;

         mem[cur].next = prev;

         prev = cur;

         cur = tmp;

         k--;

     }

     mem[head].next = cur;

     return prev;

 }

 int reverse(int head, int k, unordered_map<int, Node>& mem, int n) {

     if (head == -) {

         return -;

     }

     int nhead = -;

     int cur = head;

     int pre = -; 

     while (cur != -) {

         int t = reverse_help(cur, k, mem);

         if (nhead == -) {

             nhead = t;

         }

         if (pre != -) {

             mem[pre].next = t;

         }

         pre = cur;

         cur = mem[cur].next;

         n -= k;

         if (n < k) {

             break;

         }

     }

     return nhead;

 }

 void print(int head, unordered_map<int, Node>& mem) {

     int cur = head;

     while(cur != -) {

         Node& cnode = mem[cur];

         if (cnode.next != -) {

             printf("%05d %d %05d\n", cur, cnode.data, cnode.next);

         } else {

             printf("%05d %d %d\n", cur, cnode.data, cnode.next);

         }

         cur = mem[cur].next;

     }

 }

 int count(int head, unordered_map<int, Node>& mem) {

     int cnt = ;

     int cur = head;

     while(cur != -) {

         cnt++;

         cur = mem[cur].next;

     }

     return cnt;

 }

 int main() {

     int head, n, k;

     scanf("%d%d%d", &head, &n, &k);

     unordered_map<int, Node> mem;

     for (int i=; i<n; i++) {

         int addr, data, next;

         scanf("%d%d%d", &addr, &data, &next);

         mem.insert(make_pair(addr, Node(data, next)));

     }

     cout<<"===="<<endl;

     print(head, mem);

     cout<<"===="<<endl;

     head = reverse(head, k, mem, count(head, mem));

     print(head, mem);

     return ;

 }