#862. DISTANCE - Khoảng cách

Cho một cây ban đầu có đỉnh, cạnh, người ta xóa hết các cạnh của cây, sau đó thực hiện truy vấn, mỗi truy vấn thuộc một trong hai loại:

• Loại : Cho bởi bộ số nghĩa là truy vấn thực hiện thêm cạnh có trọng số giữa hai đỉnh . Ví dụ: tức là thêm cạnh có trọng số từ đến . Cạnh được thêm vào đảm bảo không xuất hiện chu trình.
• Loại : cho bởi bộ số , hỏi độ dài đường đi ngắn nhất từ đỉnh đến đỉnh hiện tại bằng bao nhiêu. Nếu không có đường đi thì in ra .

Các truy vấn là xen kẽ nhau. Hãy trả lời cho các truy vấn loại .

Dữ liệu vào:

• Dòng đầu tiên là hai số và ;
• dòng sau thể hiện các truy vấn có thể loại hoặc loại .

Dữ liệu ra:

• In ra câu trả lời cho các truy vấn loại theo thứ tự của nó.

Ví dụ:

Dữ liệu vào:

5 8
1 1 2 5
1 3 5 7
2 2 4
1 5 4 1
2 3 4
1 1 5 6
2 1 4
2 2 4

Dữ liệu ra:

-1
8
7
12

Giới hạn:

• .