Nâng cấp

Đất nước Z gồm có \(n\) thành phố và \(n - 1\) con đường hai chiều giữa các thành phố. Hệ thống đường đảm bảo từ thành phố bất kỳ có thể đi đến được thành phố bất kỳ khác. Do nhu cầu xây dựng phát triển hạ tầng trong thời gian tới tăng cao, Bộ Giao thông đã thu thập, đánh giá có \(m\) dự án cần vận chuyển giữa các cặp thành phố, cụ thể dự án thứ \(k\ (1 \le k \le m)\) cho biết nhu cầu đi lại giữa hai thành phố \(i_k\) và \(j_k\) là \(w_k\).

Bộ Giao thông dự định sẽ nâng cấp một tuyến đường được mô tả bằng hai thành phố \(u, v\), khi đó toàn bộ các con đường nằm trên tuyến đường đi lại giữa hai thành phố \(u, v\) đều sẽ được nâng cấp. Hiệu quả việc nâng cấp tuyến đường giữa hai thành phố
\(u, v\) được tính bằng tổng các \(w_k\) nếu \(i_k, j_k\) thuộc trên đường đi lại giữa \(u, v\ (1 \le k \le m)\).

Yêu cầu: Tìm tuyến đường để nâng cấp có hiệu quả là lớn nhất.

Input

• Dòng đầu chứa số nguyên dương \(n\).
• Tiếp theo là \(n- 1\) dòng, mỗi dòng chứa hai số mô tả \(n-1\) con đường.
• Dòng tiếp theo chứa số nguyên dương \(m\).
• Tiếp theo là \(m\) dòng, dòng thứ \(k\) chứa ba số nguyên dương \(i_k, j_k, w_k\ (1 \le i_k, j_k \le n; w_k \le 1000)\).

Output

• Gồm một số nguyên là hiệu quả nâng cấp lớn nhất tìm được.

Example

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

25

Scoring

• Có \(20\%\) số test ứng với \(20\%\) số điểm của bài có \(n \le 100; m \le 100\).
• Có \(20\%\) số test khác ứng với \(20\%\) số điểm của bài có \(n \le 100; m \le 10^5\).
• Có \(30\%\) số test khác ứng với \(30\%\) số điểm của bài có \(n \le 1000; m \le 10^5\).
• Có \(20\%\) số test khác ứng với \(20\%\) số điểm của bài có \(n \le 20000; m \le 10^5\).
• Có \(10\%\) số test còn lại ứng với \(10\%\) số điểm của bài có \(n,m \le 2 \times 10^5\).