Nhân chuyến thi Tin học tại HDCity, BT có dịp đi thăm bạn bè, HDCity có \(N\) khu vực khác nhau được nối bởi \(N -1\) con đường 2 chiều nối chúng, biết rằng giữa 2 khu vực 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) và chi phí để di chuyển trên con đường trực tiếp nối khu vực \(x\) và thành phố \(y\) là \(C[x,y]\).

Vì ban ngày, BT phải đi thi, nên BT 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 khu vực \(A\) và khu vực \(B\). BT 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à BT thì không được đi quá khuya. Rất may, BT có 1 người bạn thân là Supermen, 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 BT 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 BT đã đi thăm bạn xong)

Yêu cầu: Biết rằng BT ở tại khách sạn (khu vực 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 BT vào mỗi tối? (Không tính thời gian từ \(B\) quay trở về \(1\)).

Input

• Dòng 1: Chứa 1 số nguyên dương N tương ứng là số khu vực.
• \(N-1\) dòng tiếp theo, dòng thứ \(i\) \((i = 1 .. N)\) chứa 2 số nguyên dương \(𝑝[𝑖]\) và \(𝑐[𝑖]\) tương ứng có nghĩa có con đường nối thành phố \(𝑖 + 1\) với thành phố \(𝑝[𝑖]\) và thời gian di chuyển là \(𝑐[𝑖]\).
• Dòng tiếp theo chứa số nguyên dương \(Q\) tương ứng là số buổi tối BT ở khách sạn.
• 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\) BT muốn thăm người bạn ở khu vực \(A_i\), sau đó thăm người bạn ở khu vực \(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\).
• Các số trên một dòng của input file được ghi cách nhau bởi dấu cách

Output

• Viết trên \(Q\) dòng, dòng thứ \(𝑖\) là thời gian ngắn nhất mà BT có thể đi thăm \(A_i\) rồi đến thăm \(B_i\) trong truy vấn thứ \(i\) theo thứ tự.

Scoring

• \(2 \leq N \leq 10^6, 1 \leq Q \leq 10^5\)
• \(0 \leq C_i \leq 1000, 0 \leq T \leq 10^6, 2 \leq A, B \leq N\).
• \(20\%\) số điểm tương ứng \(N \leq 100, Q \leq 10\).
• \(40\%\) số điểm tương ứng \(N \leq 3000, Q \leq 10\).
• \(60\%\) số điểm tương ứng \(N \leq 10^6, Q \leq 10\).

Example

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

8
17