Cho đơn đồ thị vô hướng liên thông gồm ~n~ đỉnh và ~m~ cạnh. Bạn hãy trả lời ~q~ truy vấn dạng:

• ~0~ ~x~: Tìm độ dài đường đi ngắn nhất từ đỉnh ~1~ đến đỉnh ~x~.
• ~1~: Tìm giá trị của cây khung nhỏ nhất trên đồ thị

Dữ liệu vào:

• Dòng đầu ghi 3 số nguyên ~n,m,q~ ~(1≤n,m≤10^5)~
• ~m~ dòng tiếp theo mỗi dòng ghi 3 số nguyên ~u,v,c~ ~(1≤u,v≤n;1≤c≤10^9)~ cho biết cạnh ~(u,v)~ có trọng số ~c~
• ~q~ dòng tiếp theo, mỗi dòng cho biết thông tin của một truy vấn và bắt đầu bằng số nguyên ~k~ ~(k=0..1)~ cho biết loại truy vấn, nếu ~k=0~ thì tiếp theo ghi số nguyên ~x~ ~(1≤x≤n)~

Kết quả:

• Ghi trên ~q~ dòng, mỗi dòng ghi một số nguyên là kết quả của truy vấn tương ứng trong input.

Ví dụ:

Input

4 5 3
1 2 1
2 4 2
1 4 6
2 3 6
3 4 3
0 2
1
0 3 

Output

1
6
6 

Ràng buộc:

• Có 50% số test có ~q≤2~ và chỉ có truy vấn dạng ~0~ ~x~
• Có 30% số test khác có ~q≤10^5~ và chỉ có truy vấn dạng ~0~ ~x~
• Có 20% số test còn lại có ~q≤10^5~ và có cả hai loại truy vấn.