Cho đồ thị vô hướng liên thông gồm ~n~ đỉnh và ~n - 1~ cạnh. Cạnh thứ ~i~ nối đỉnh ~u_i~ với đỉnh ~v_i~ có độ dài ~w_i~. Cho ~Q~ truy vấn thuộc một trong hai loại:

• Loại 1: ~1 \ x \ y~: In độ dài đường đi ngắn nhất từ đỉnh ~x~ đến đỉnh ~y~.
• Loại 2: ~2 \ x \ y \ k~: In đỉnh thứ ~k~ trên đường đi ngắn nhất từ ~x~ đến ~y~.

Yêu cầu: Với mỗi truy vấn, tìm kết quả tương ứng.

Input

• Dòng đầu chứa hai số ~n, Q~ (~1 \le n, Q \le 10^5~).
• ~n - 1~ dòng sau, dòng thứ ~i + 1~ (~1 \le i \le n - 1~) chứa ba số nguyên ~u_i, v_i, w_i~ (~1 \le u_i, v_i \le n~, ~1 \le w_i \le 10^6~).
• ~Q~ dòng cuối, mỗi dòng chứa thông tin một truy vấn thuộc một trong hai loại ở trên. Dữ liệu đảm bảo truy vấn loại 2 tồn tại đáp số.

Output

• Tương ứng với mỗi truy vấn, ghi kết quả tìm được trên một hàng.

Sample Input 1

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

Sample Output 1

5
3