(ddack.*)

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 \leq n,m \leq 10^{5})\)

+ \(m\) dòng tiếp theo mỗi dòng ghi 3 số nguyên \(u,\ v,\ c\ (1 \leq u,v \leq n;1 \leq c \leq 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 \leq x \leq 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.

Ràng buộc:

+ Có 50% số test có \(q \leq 2\) và chỉ có truy vấn dạng \(0\ x\)

+ Có 30% số test khác có \(q \leq 10^{5}\) và chỉ có truy vấn dạng \(0\ x\)

+ Có 20% số test còn lại có \(q \leq 10^{5}\) và có cả hai loại truy vấn.