Quy hoạch mạng lưới

Vương quốc Đại Việt có \(n\) thành phố được đánh số từ \(1\) đến \(n\). Các thành phố được kết nối với nhau bằng \(n-1\) con đường hai chiều, tạo thành một mạng lưới đảm bảo luôn có đường đi giữa hai thành phố bất kỳ. Con đường thứ \(i\) nối thành phố \(u\) và thành phố \(v\) có thời gian di chuyển là \(d(u, v)\).

Sau một trận bão lớn, chính quyền muốn thực hiện nâng cấp các con đường để giảm thiểu thời gian di chuyển. Việc nâng cấp chỉ áp dụng cho các con đường có thời gian di chuyển lớn hơn \(0\). Mỗi lần nâng cấp sẽ giảm thời gian di chuyển trên một con đường đi đúng 1 đơn vị.

Với mỗi thành phố \(u\), ta định nghĩa \(t(v)\) là thời gian di chuyển ngắn nhất từ \(u\) đến \(v\). Tổng thời gian di chuyển ngắn nhất từ thành phố \(u\) đến tất cả các thành phố khác được gọi là \(f(u)\), được tính bằng công thức: \(f(u) = \sum_{v=1}^n t(v)\).

Bạn được phép nâng cấp tổng cộng \(k\) lần. Sau khi nâng cấp, thời gian di chuyển trên các con đường đã giảm, và giá trị \(f(u)\) cũng sẽ thay đổi. Giá trị \(f(u)\) nhỏ nhất có thể sau khi nâng cấp được ký hiệu là \(T(u, k)\).

Yêu cầu: Cho \(q\) truy vấn, mỗi truy vấn gồm ba số \(u, L, H\). Hãy tính giá trị \(S = \left(\sum_{k=L}^{H} T(u, k)\right) \pmod{10^9 + 7}\).

Input

• Dòng đầu tiên chứa một số nguyên \(n\) (\(1 \le n \le 200000\)).
• \(n-1\) dòng tiếp theo, mỗi dòng chứa ba số \(u, v, d(u, v)\) (\(1 \le u, v \le n, d(u, v) \le 10^8\)) mô tả một con đường.
• Dòng tiếp theo chứa một số nguyên \(q\) (\(1 \le q \le 200000\)) là số lượng câu hỏi truy vấn.
• Mỗi dòng trong \(q\) dòng tiếp theo chứa ba số nguyên \(u, L, H\) (\(1 \le u \le n, 0 \le L \le H \le 10^9\)) mô tả một truy vấn.

Output

• Ghi ra \(q\) dòng, mỗi dòng là kết quả cho một truy vấn tương ứng.

Example

5
1 2 3
2 4 2
1 3 4
1 5 6
4
2 4 5
1 1 1
5 20 20
4 0 0

21
16
0
27