Cho cây ~T~ gồm ~n~ nút và ~Q~ truy vấn. Các nút của cây được đánh số thứ tự bắt đầu từ 0 và mỗi cạnh của cây được gán một trọng số. Một truy vấn là bộ năm số nguyên ~\{a, b, c, d, e\}~ đôi một khác nhau. Câu trả lời cho mỗi truy vấn là tổng trọng số nhỏ nhất của cây con chứa năm nút ~a, b, c, d, e~.

Yêu cầu: Viết chương trình trả lời ~Q~ truy vấn, với mỗi truy vấn đưa ra tổng trọng số nhỏ nhất của cây con tương ứng.

Input

• Dòng đầu tiên chứa số nguyên dương ~n~;
• ~n - 1~ dòng tiếp theo, mỗi dòng gồm ba số nguyên ~u, v, w~ có nghĩa là nút ~u~ nối với nút ~v~ và cạnh ~(u, v)~ có trọng số là ~w~, dữ liệu luôn đảm bảo ~0 \le u, v < n~ và ~1 \le w \le 1000~;
• Dòng tiếp theo chứa số nguyên dương ~Q~;
• ~Q~ dòng tiếp theo, mỗi dòng gồm năm số nguyên ~a, b, c, d, e~.

Output

• Ghi ra ~Q~ dòng, mỗi dòng là câu trả lời tương ứng cho các truy vấn trong tệp dữ liệu vào.

Sample Input 1

6
4 0 4
0 1 2
1 3 9
3 5 1
3 2 5
2
4 0 3 5 2
0 4 1 3 5

Sample Output 1

21
16