Tại nước Cộng hòa VOI, có \(N\) thành phố được đánh số từ \(1\) đến \(N\). Các thành phố được kết nối với \(N - 1\) đường hai chiều. Người dân ở Cộng hòa VOI đang đi lại giữa các thành phố bằng những con đường này. Họ có thể đi lại giữa hai thành phố bất kỳ bằng cách đi qua một hoặc một số con đường.

Ông PVH là ứng cử viên tổng thống của Cộng hòa VOI. Tất nhiên, để trở thành tổng thống, ông ta phải thực hiện chiến dịch tranh cử tổng thống. Thư ký của ông đã lên kế hoạch cho \(M\) chiến dịch tranh cử. Trong kế hoạch thứ \(i\), ông PVH sẽ đi từ thành phố \(A_i\) đến thành phố \(B_i\), sử dụng số con đường tối thiểu và phát biểu trước công chúng tại mỗi thành phố trên đường đi (bao gồm thành phố \(A_i\) và thành phố \(B_i\)). Bởi vì thư ký của ông ấy rất giỏi, nên anh ta biết rằng ông PVH sẽ nhận được phiếu \(C_i\) nếu kế hoạch thứ \(i\) được thực hiện. Có thể thực hiện nhiều kế hoạch.

Tuy nhiên, những người ở Cộng hòa VOI rất thiếu kiên nhẫn. Nếu ông PVH phát biểu trước công chúng nhiều lần trong cùng một thành phố, ông sẽ mất sự ủng hộ từ người dân trong Cộng hòa VOI.

Bởi vì ông PVH muốn trở thành tổng thống, ông ấy muốn nhận được càng nhiều phiếu bầu càng tốt. Vì bạn là siêu lập trình viên ở Cộng hòa VOI, ông ấy đã yêu cầu bạn viết một chương trình tính toán số phiếu bầu tối đa mà ông PVH có thể nhận được trong cuộc bầu cử tổng thống với giả định rằng ông ấy sẽ không phát biểu trước công chúng nhiều lần trong cùng một thành phố.

Với \(N\) là số thành phố ở Cộng hòa VOI, thông tin về các con đường, \(M\) là số kế hoạch cho chiến dịch bầu cử và thông tin của từng kế hoạch, hãy viết một chương trình tính toán số phiếu bầu tối đa mà ông PVH có thể nhận được cuộc bầu cử tổng thống.

Input:

• Dòng đầu tiên chứa số nguyên \(N\) \((2 \leq n \leq 10^5)\) là số thành phố tại nước cộng hoà VOI

• \(N - 1\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(u, v\) \((1 \leq u, v \leq N, u \neq v)\) thể hiện con đường nối giữa thành phố \(u\) và thành phố \(v\).

• Dòng tiếp theo chứa số nguyên \(M\) \((1 \leq M \leq 10^5)\) là số kế hoạch tranh cử

• \(M\) dòng tiêp theo, dòng thứ \(i\) chứa ba số nguyên \(A_i, B_i, C_i\) \((1 \leq A_i, B_i \leq N, A_i \neq B_i, 1 \leq C_i \leq 10^4)\) thể hiện kế hoạch thứ \(i\)

Output:

• Gồm một dòng duy nhất là số phiếu tối đa ông PVH có thể nhận được

Scoring:

Bộ test của bài được chia làm các subtask như sau:

• Subtask 1 (10 điểm): \(M \leq 15\)
• Subtask 2 (5 điểm): \(X_i = i,Y_i = i + 1, C_i = 1\)
• Subtask 3 (5 điểm): \(X_i = i,Y_i = i + 1\)
• Subtask 4 (30 điểm): \(C_i = 1\)
• Subtask 5 (10 điểm): \(N \leq 1000, M \leq 1000\)
• Subtask 6 (40 điểm): Không có ràng buộc gì thêm.

Điểm tối đa của bài là \(100\) điểm.

Example