Cho đơn đồ thị vô hướng \(N\) đỉnh và \(M\) cạnh, trọng số các cạnh đều nguyên dương. Có \(2\) loại câu hỏi:

• \(0\) \(u\) \(v\): Cho biết đường đi ngắn nhất từ \(u\) đến \(v\) có độ dài bao nhiêu
• \(1\) \(u\) \(v\): Hãy chỉ ra \(1\) đường đi ngắn nhất từ \(u \rightarrow v\)

Bài cơ bản này nhằm kiểm tra kỹ năng xây dựng các module chương trình con dành cho truy vết \(1\) cách hợp lý, sử dụng nhuần nhuyễn chương trình con, lời gọi hàm.

Dữ liệu vào

• Dòng đầu tiên: \(3\) số nguyên \(N,M,K\)
• \(M\) dòng tiếp theom dòng thứ \(i\) gồm \(3\) số nguyên dương \(u,v,c\) cho biết \((u,v)\) có trọng số là \(c\)
• \(K\) dòng tiếp theo là \(K\) câu hỏi, dòng thứ \(j\) sẽ có định dạng như đã nêu ở trên.

Dữ liệu ra

• Ứng với mỗi câu hỏi trong \(K\) câu hỏi thì ta phải trả lời trên mỗi dòng như sau.
• Câu hỏi \(0\) \(u\) \(v\): Cho biết đường đi ngắn nhất từ \(u \rightarrow v\) có độ dài bao nhiêu
• \(1\) \(u\) \(v\): Ghi ra số đầu tiên là số \(X\) là số đỉnh trên đường đi ngắn nhất này, tiếp đó ghi ra \(X\) số là chỉ số các đỉnh theo thứ tự xuất hiện trên hành trình.

Input 1

3 3 2
1 2 3
2 3 1
1 3 5
0 1 2
1 1 3

Output 1

3
3 1 2 3