Sau khi bị pain hack pay làng thì làng lá hiện đang trong công cuộc xây dựng lại. Hôm nay Uzumaki bin9638, hokage của làng lá và Uchiha algorit, người còn lại cuối cùng của tộc Uchiha đang lên kế hoạch xây dựng lại làng. Ngôi làng gồm \(n\) ngôi nhà được đánh số từ \(1\) tới \(n\) \((n \le 2*10^5)\) và có \(n-1\) con đường nối \(2\) ngôi nhà bất kì sao cho tất của các nhà đều được liên thông với nhau, mỗi con đường sẽ có độ dài \(w\) \((w \le 10^9)\).

Ngôi làng bây giờ có \(q\) \((q \le 2*10^5)\) bộ ba ngôi nhà wibu. Với mỗi bộ ba ngôi nhà này bin9638 và algorit muốn tính giá trị nhỏ nhất của \(wibu(a,x)+wibu(b,x)+wibu(c,x)\) với \(wibu(u,v)\) là khoảng cách để đi từ nhà \(u\) đến nhà \(v\). Ở đây \(x\) là \(1\) ngôi nhà bất kì trong làng.

Input

• Dòng đầu tiên là số \(n\).
• \(n-1\) dòng tiếp theo mỗi dòng là \(3\) số \(u, v, w\) biểu thị có đường nối \(2\) nhà \(u\) và \(v\) với độ dài \(w\).
• Dòng tiếp theo là số \(q\).
• \(q\) dòng tiếp theo là các truy vấn, mỗi truy vấn gồm \(3\) số \(a,b,c\).

Output

• Gồm \(q\) dòng là kết quả cho các truy vấn.

Scoring

• Subtask \(1\) (\(30\%\) số điểm): \(n , q \le 15\)
• Subtask \(2\) (\(30\%\) số điểm): \(n , q \le 1000\)
• Subtask \(3\) (\(40\%\) số điểm): \(n , q \le 2*10^5\)

Example

4
1 2 1
2 3 2
1 4 3
2
1 2 3 
1 2 4 

3
4