Nhân chuyến thi khảo sát đội tuyển HSG Tin học 3HB, HD có dịp về thăm quê, quê hương của HD có ~N~ ngôi nhà và ~N-1~ con đường 2 chiều nối chúng, biết rằng:

• Giữa ~2~ thành phố bất kỳ đều có đường đi trực tiếp hoặc gián tiếp (đi qua một số con đường trung gian).
• Chi phí để di chuyển trên con đường nối thành phố ~x~ và thành phố ~y~ là ~c[x,y]~.

Vì ban ngày, HD phải thi HSG tin học, nên HD chỉ có thể đến thăm bạn vào chiều tối, mỗi buổi tối, anh ấy xác định ~2~ người bạn cần phải thăm đang sống tại thành phố ~A~ và thành phố ~B~. HD muốn đến thăm người bạn ~A~ trước, sau đó di chuyển đến thăm người bạn ~B~. Chi phí về thời gian là rất lớn mà HD thì không được đi quá khuya (vì còn phải nghỉ ngơi để sáng hôm sau còn thi cho tốt và giành giải cao, phần thưởng lớn). Rất may, HD có một người bạn thân là HP, có thể dựng một con đường nối trực tiếp ~A~ và ~B~ với thời gian đi là ~T~ để giúp HD giảm thiểu thời gian di chuyển từ nơi thi, đến thăm bạn ~A~ sau đó thăm bạn ~B~ (con đường này chỉ được xây dựng vào buổi tối, và hủy bỏ vào buổi sáng, sau khi HD đã đi thăm bạn xong).

Yêu cầu: Biết rằng HD ở lại quê hương (tại thành phố ~1~) trong ~Q~ buổi tối, bạn hãy tính thời gian đi thăm bạn ít nhất của HD vào mỗi tối? (Không tính thời gian từ ~B~ quay trở về ~1~)

Làm rõ: Trong trường hợp đi qua ~B~ trước khi qua ~A~, HD vẫn phải đi theo đúng thứ tự từ ~A~ đến ~B~, không được dừng ở ~B~ khi chưa đi qua ~A~ (nói cách khác, phải đi theo dạng ~1→B→A→B~).

Input

Vào từ file FRIENDS.INP:

• Dòng đầu chứa một số nguyên dương ~N\ (N \le 10^6)~ tương ứng là số thành phố.
• ~N–1~ dòng tiếp theo, dòng thứ ~i\ (i=1..N-1)~ chứa 2 số nguyên ~p[i]~ và ~c[i]~ tương ứng có nghĩa có con đường nối thành phố ~i+1~ với thành phố ~p[i]~ và thời gian di chuyển là ~c[i]\ (0 \le c[i] \le 1000)~.
• Dòng tiếp theo chứa số nguyên dương ~Q\ (Q \le 10^5)~ tương ứng là số buổi tối HD ở lại thăm quê.
• ~Q~ dòng tiếp theo, dòng thứ ~i~ ghi ba số nguyên dương ~A_i,B_i,T_i~ thể hiện ở tối thứ ~i~ HD muốn thăm người bạn ở thành phố ~A_i~, sau đó thăm người bạn ở thành phố ~B_i~ và khi xây dựng một con đường tưởng tượng nối ~A_i,B_i~ thì thời gian di chuyển trên con đường này là ~T_i~. ~(2\le A, B \le N,\ 0 \le T \le 10^6)~

Output

Ghi ra tệp FRIENDS.OUT:

• Gồm ~Q~ dòng, dòng thứ ~i~ là thời gian ngắn nhất mà HD có thể đi thăm ~A_i~ rồi đến thăm ~B_i~ trong truy vấn thứ ~i~ theo thứ tự.

Subtasks

• ~20\%~ số test có ~N \le 100,\ Q \le 10~.
• ~20\%~ số test có ~N \le 3000,\ Q \le 10~.
• ~20\%~ số test có ~Q \le 10~.
• ~40\%~ số test còn lại không có ràng buộc gì thêm.

Sample Input 1

4
1 4
2 3
2 5
2
3 4 1
4 3 10

Sample Output 1

8
17

Giải thích

• Ở truy vấn 1: ~1→2→3→4~.
• Ở truy vấn 2: ~1→2→4→2→3~.