Có \(n\) hòn đảo biệt lập. Trước đây, người dân di chuyển giữa các đảo bằng tàu thuyền, nhưng điều đó bây giờ không còn thuận tiện nữa. Chính quyền địa phương quyết định xây dựng một hệ thống cầu nối để giúp việc đi lại giữa các đảo trở nên dễ dàng hơn.

Tuy nhiên, thay vì xây dựng ngay lập tức, họ muốn thực hiện một số giả định thử nghiệm trước khi thi công thực tế. Và một lần nữa, Bờm được giao trọng trách quan trọng này.

Trong mô hình thử nghiệm mỗi hòn đảo được xem là một đỉnh trong đồ thị, mỗi cây cầu sẽ là một cạnh có trọng số là độ dài của cây cầu. Ban đầu chưa có cây cầu nào, chính quyền sẽ liên tục đưa ra các truy vấn để thử nghiệm việc xây cầu và kiểm tra khoảng cách giữa các đảo.

Bờm cần giúp chính quyền thực hiện \(Q\) truy vấn, mỗi truy vấn thuộc một trong hai loại:

• Xây dựng cầu giả định: Cho trước hai đảo \(𝑢\) và \(𝑣\), chính quyền muốn thử nghiệm việc xây một cây cầu có độ dài \(𝑤\) giữa hai đảo này. Tuy nhiên, hệ thống cầu phải đảm bảo không có chu trình.

• Tính khoảng cách di chuyển: Người dân muốn biết độ dài ngắn nhất khi di chuyển giữa hai đảo \(𝑢\) và \(𝑣\). Nếu hai đảo này chưa được nối với nhau bằng cầu, thì câu trả lời là \(-1\).

Dữ liệu:

• Dòng đầu tiên là số hai số nguyên dương \(n,Q (1≤n,Q≤2.10^5 )\) tương ứng là số lượng hòn đảo và số lượng truy vấn.

• \(Q\) dòng sau thể hiện các truy vấn có thể loại \(1\) hoặc loại \(2\).

Kết quả:

• Ghi các câu trả lời cho các truy vấn loại 2 theo thứ tự của nó trong truy vấn tương ứng.

Ràng buộc: \(1≤n,Q≤2.10^5; 1≤w≤10^4\)

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