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 :

1 \(x\ y\): In độ dài đường đi ngắn nhất từ đỉnh \(x\) đến đỉnh \(y.\)

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.

Dữ liệu vào:

- Dòng đầu chứa hai số \(n,\ Q\ (1 \leq n,\ Q \leq 10^{5})\)

- \(n - 1\ \)dòng sau, dòng thứ \(i + 1\ (1 \leq i \leq n - 1)\) chứa ba số nguyên \(u_{i},\ v_{i},\ w_{i\ }(1 \leq u_{i},\ v_{i},\ \leq n,\ 1 \leq w_{i\ } \leq 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ố.

Dữ liệu ra:

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

Ví dụ:

Input	Output
6 2 1 2 1 2 4 1 2 5 2 1 3 1 3 6 2 1 4 6 2 4 6 4	5 3

Các giới hạn:

• Subtask 1: 30% tổng số test có \(n \leq 1000,\ Q \leq 10.\)

• Subtask 2: 30% tổng số test tiếp theo có \(n,\ Q \leq 10^{5}\) và tất cả các truy vấn là loại 1.

• Subtask 3: 40% tổng số test còn lại không có ràng buộc gì thêm.