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~ tới ~v~ có độ dài là 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.

Input

Dòng ~1~: ~3~ số nguyên ~N~, ~M~, ~K~. ~\left(1 \leq N \leq 100, 1 \leq M \leq \frac{N(N-1)}{2}, 1 \leq K \leq 1000\right)~

~M~ dòng tiếp theo, dòng thứ ~i~ gồm ~3~ số nguyên dương ~u~, ~v~, ~c~ cho biết cạnh (~u~, ~v~) có trọng số là ~c~ ~(1 \leq c \leq 10000)~

~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.

Output

Ứ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~: Ghi ra ~1~ số nguyên duy nhất là độ dài đường đi ngắn nhất từ ~u \rightarrow v~.

Câu hỏi ~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.

Sample Input

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

Sample Output

3
3 1 2 3

Note

Download test và solution tại đây.

Lưu ý: Do thay đổi về trình chấm (trình chấm mới không chấp nhận 1 đỉnh tự quay lại chính nó nếu không có cạnh ở input), do đó solution ở trên sẽ không AC ở VNOJ.