Cho một cây có trọng số gồm ~N~ đỉnh, ~N-1~ cạnh, đỉnh gốc là đỉnh 1. Có ~Q~ truy vấn, mỗi truy vấn cho dưới dạng ~(u, v, x)~ hỏi đường đi có trọng số lớn nhất giữa cặp ~(u, v)~ trên cây nếu được phép nối một đỉnh thuộc cây con gốc ~u~ với một đỉnh cây con gốc ~v~ bởi một cạnh có trọng số là ~x\ (x \le 0)~ bằng bao nhiêu?

Input

Vào từ file TREEDGE.INP:

• Dòng đầu ghi số ~N, Q\ (1 \le N,Q \le 2\times 10^5)~ là số đỉnh của cây, số truy vấn.
• ~N-1~ dòng tiếp ghi bộ số ~u, v, w\ (1 \le u, v \le N,\ |w| \le 10^9)~ mô tả các cạnh của cây, đỉnh đầu ~u~, đỉnh cuối ~v~, trọng số ~w~ của cạnh.
• ~Q~ dòng tiếp theo ghi bộ số ~u, v, x~ thể hiện truy vấn tìm trọng số đường đi từ ~u~ đến ~v~ lớn nhất khi được thêm một cạnh trọng số ~x\ (0\le x \le 10^9)~ nối một đỉnh thuộc cây con gốc ~u~ với một đỉnh thuộc cây con gốc ~v~.

Output

Ghi ra tệp TREEDGE.OUT:

• Ghi ~Q~ số là kết quả của từng truy vấn theo thứ tự, mỗi số viết trên một dòng.

Sample Input 1

7 3
1 2 1
1 3 -2
2 4 3
2 5 -4
5 7 5
3 6 6
2 3 1
5 4 2
5 6 0

Sample Output 1

10
7
5

Giải thích