Cho một cây ban đầu có ~N~ đỉnh, ~N-1~ cạnh, người ta xóa hết các cạnh của cây.

Thực hiện ~Q~ truy vấn, mỗi truy vấn thuộc 1 trong 2 loại:

• Loại 1: Cho bởi bộ ~4~ số ~(1, u, v, w)~ nghĩa là truy vấn thực hiện thêm cạnh có trọng số ~w~ giữa ~2~ đỉnh ~u, v~.

Ví dụ: ~(1, 1, 3, 4)~ thêm cạnh có trọng số ~4~ từ ~1~ đến ~3~. Cạnh được thêm vào đảm bảo không xuất hiện chu trình.

• Loại 2: cho bởi bộ ~3~ số ~(2,u,v)~ Hỏi độ dài đường đi ngắn nhất từ đỉnh ~u~ đến đỉnh ~v~ hiện tại bằng bao nhiêu. Nếu không có đường đi thì in ra ~-1~.

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

Input

• Dòng đầu tiên là số N và Q.
• In ra câu trả lời cho các truy vấn loại 2 theo thứ tự của nó.

Output

• Gồm một dòng chứa một số là giá trị ~𝑊~ nhỏ nhất tìm được.
• Q dòng sau thể hiện các truy vấn có thể loại 1 hoặc loại 2.

Giới hạn

• ~1 ≤ 𝑁~
• ~𝑄 ≤ 2.1e5~
• ~1 ≤ 𝑤 ≤ 10~

Sample Input

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

Sample Output

-1
8 7
12