Cộng hòa JOI có \(N\) thành phố, được đánh số từ \(1\) đến \(N\). Các thành phố được nối bởi \(N-1\) con đường hai chiều. Người dân có thể đi giữa hai thành phố bất kỳ qua một hoặc nhiều con đường.

Ông IOI là ứng cử viên tổng thống Cộng hòa JOI. Để trở thành tổng thống, ông phải tiến hành chiến dịch tranh cử. Thư ký của ông đã lập \(M\) kế hoạch. Trong kế hoạch thứ \(i\), ông IOI đi từ thành phố \(A_i\) đến thành phố \(B_i\) qua số con đường ít nhất và diễn thuyết công khai tại mọi thành phố trên đường đi, bao gồm cả \(A_i\) và \(B_i\). Nếu thực hiện kế hoạch thứ \(i\), ông IOI sẽ nhận được \(C_i\) phiếu bầu. Ông có thể thực hiện nhiều kế hoạch.

Tuy nhiên, người dân Cộng hòa JOI rất thiếu kiên nhẫn. Nếu ông IOI diễn thuyết công khai nhiều hơn một lần tại cùng một thành phố, ông sẽ mất sự ủng hộ của họ.

Ông IOI muốn nhận được nhiều phiếu bầu nhất có thể, với điều kiện không diễn thuyết quá một lần tại bất kỳ thành phố nào. Hãy tính số phiếu bầu lớn nhất ông có thể nhận được.

Dữ liệu vào

Đọc dữ liệu từ đầu vào chuẩn theo định dạng sau:

• Dòng đầu chứa số nguyên \(N\), số thành phố của Cộng hòa JOI.
• Trong \(N-1\) dòng tiếp theo, dòng thứ \(i\) (\(1 \le i \le N-1\)) chứa hai số nguyên \(X_i\), \(Y_i\). Con đường thứ \(i\) nối thành phố \(X_i\) và thành phố \(Y_i\).
• Dòng tiếp theo chứa số nguyên \(M\), số kế hoạch tranh cử.
• Trong \(M\) dòng tiếp theo, dòng thứ \(i\) (\(1 \le i \le M\)) chứa ba số nguyên \(A_i\), \(B_i\), \(C_i\). Trong kế hoạch thứ \(i\), ông IOI đi từ \(A_i\) đến \(B_i\) theo đường có ít cạnh nhất và nhận được \(C_i\) phiếu bầu nếu thực hiện kế hoạch này.

Dữ liệu ra

In ra một số nguyên duy nhất: số phiếu bầu lớn nhất ông IOI có thể nhận được.

Ràng buộc

• \(2 \le N \le 100\,000\).
• \(1 \le X_i, Y_i \le N\) (\(1 \le i \le N-1\)).
• \(X_i \ne Y_i\) (\(1 \le i \le N-1\)).
• Có thể đi giữa hai thành phố bất kỳ qua một hoặc nhiều con đường.
• \(1 \le M \le 100\,000\).
• \(1 \le A_i, B_i \le N\) (\(1 \le i \le M\)).
• \(A_i \ne B_i\) (\(1 \le i \le M\)).
• \(1 \le C_i \le 10\,000\) (\(1 \le i \le M\)).

Phân nhóm

• Nhóm 1 (10 điểm)

• \(M \le 15\).

• Nhóm 2 (5 điểm)

• \(X_i = i\) và \(Y_i = i+1\) (\(1 \le i \le N-1\)).

• \(C_i = 1\) (\(1 \le i \le M\)).

• Nhóm 3 (5 điểm)

• \(X_i = i\) và \(Y_i = i+1\) (\(1 \le i \le N-1\)).

• Nhóm 4 (30 điểm)

• \(C_i = 1\) (\(1 \le i \le M\)).

• Nhóm 5 (10 điểm)

• \(N \le 1\,000\).

• \(M \le 1\,000\).

• Nhóm 6 (40 điểm)

Không có ràng buộc bổ sung.

Ví dụ

7
3 4
6 5
2 7
1 5
7 5
4 5
5
4 3 10
5 6 5
2 6 9
7 2 2
1 3 8

19

8
1 2
2 3
3 4
4 5
5 6
6 7
7 8
5
7 5 4
5 8 9
4 3 9
1 3 3
2 8 11

18

10
10 6
2 7
1 9
9 8
3 8
6 4
7 8
5 4
4 8
7
1 3 1
4 10 1
2 8 1
5 3 1
3 7 1
8 5 1
1 9 1

3

20
17 10
11 4
8 3
3 16
1 14
15 18
5 4
6 18
10 18
19 4
16 7
2 13
4 12
12 20
9 20
18 13
20 14
14 7
13 7
15
19 9 2341
13 8 6974
8 3 3339
15 17 6515
10 13 4370
1 7 8376
18 2 9272
6 7 4595
1 20 505
10 9 308
6 19 8937
2 15 5072
5 4 4217
2 4 4170
19 12 8204

29191