N = int(1e5 + 10)
e = [0] * N;ne = [0] * N

h,n,k = map(int,input().split())

for i in range(n):
    addr,data,next = map(int,input().split())
    e[addr] = data
    ne[addr] = next

li = []

i = h
while i != -1:
    li.append([i,e[i]]) # 将链表以数组的形式存储起来，这样之后的反转就很方便了
    i = ne[i]

i = 0
while i + k - 1 <= len(li) - 1:
    li[i:i + k] = li[i:i + k][::-1] # 反转
    i += k

for i in range(len(li)):
    if i == len(li) - 1:
        print(f'{li[i][0]:05d} {li[i][1]} -1')
    else:
        print(f'{li[i][0]:05d} {li[i][1]} {li[i + 1][0]:05d}')