0356 - 選挙運動 (Election Campaign)

問題

　JOI 国には N 個の街があり，それらの間は N - 1 本の双方向に通行可能な道路で結ばれている．各街にはそれぞれ 1 から N までの番号がついている．国民は道路を通ってそれらの街を移動する．どの街からどの街へも，道路を通って別の街に移動することで行き来することができる．
　このたび，IOI 氏は JOI 国の大統領選挙に出馬することになった．大統領に当選するためには，当然選挙運動が必要となる．そこで彼の秘書は，M 個の選挙運動の計画を立てた．i (1 ≤ i ≤ M) 番目の計画では，IOI 氏は街 A_i から街 B_i まで，通る道路の本数が最小となるような経路で移動し，途中 (A_i, B_i を含む) のすべての街で演説を行う．また彼の秘書はとても優秀なので，i 番目の計画を実行すると IOI 氏は C_i 票を得られることを知っている．複数の計画を実行することもできる．
　しかし困ったことに，JOI 国の国民はみな短気である．そのため，同じ街で 2 度以上演説を行った場合，彼は国民の支持を失ってしまう．
　選挙に当選したい IOI 氏は，できるだけ多くの票を獲得したい．そこで，IOI 氏は JOI 国のスーパープログラマーであるあなたに，同じ街で 2 度以上演説を行わないようにするときに得られる最大の票の数を求めるプログラムの作成を依頼した．

課題

　JOI 国の街の数 N と JOI 国の道路の情報，選挙運動の計画の数 M と各計画に関する情報が与えられたとき，IOI 氏が得られる最大の票の数を求めるプログラムを作成せよ．

入力

　標準入力から以下のデータを読み込め．

• 1 行目には整数 N が書かれている．これは，JOI 国の街の個数が N であることを表す．
• 続く N - 1 行のうちの i 行目 (1 ≤ i ≤ N - 1) には，2 つの整数 X_i, Y_i が空白を区切りとして書かれている．これは，JOI 国の i 番目の道路が，街 X_i と街 Y_i を結んでいることを表す．
• 続く 1 行には整数 M が書かれている．これは，選挙運動の計画の個数が M であることを表す．
• 続く M 行のうちの i 行目 (1 ≤ i ≤ M) には，3 つの整数 A_i, B_i, C_i が空白を区切りとして書かれている．これは，M 番目の計画では IOI 氏は街 A_i から街 B_i まで通る道の本数が最小となるように移動し，この計画を実行すると IOI 氏は C_i 票を得られることを表す．

出力

　標準出力に，IOI 氏が得られる最大の票の数を 1 行に出力せよ．

制限

　すべての入力データは以下の条件を満たす.

• 2 ≤ N ≤ 100 000．
• 1 ≤ X_i ≤ N．
• 1 ≤ Y_i ≤ N．
• X_i ≠ Y_i (1 ≤ i ≤ N - 1)．
• どの街からどの街へも，道路を通って別の街に移動することで行き来することができる．
• 1 ≤ M ≤ 100 000．
• 1 ≤ A_i ≤ N．
• 1 ≤ B_i ≤ N．
• A_i ≠ B_i (1 ≤ i ≤ M)．
• 1 ≤ C_i ≤ 10 000．

小課題

小課題 1 [10 点]

• M ≤ 15 を満たす．

小課題 2 [5 点]

• X_i = i (1 ≤ i ≤ N - 1) を満たす．
• Y_i = i + 1 (1 ≤ i ≤ N - 1) を満たす．
• C_i = 1 (1 ≤ i ≤ M) を満たす．

小課題 3 [5 点]

• X_i = i (1 ≤ i ≤ N - 1) を満たす．
• Y_i = i + 1 (1 ≤ i ≤ N - 1) を満たす．

小課題 4 [30 点]

• C_i = 1 (1 ≤ i ≤ M) を満たす．

小課題 5 [10 点]

• N ≤ 1 000 を満たす．
• M ≤ 1 000 を満たす．

小課題 6 [40 点]

　追加の制限はない．

入出力例

入力例 1

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

出力例 1

19

　この入力例の場合，1 番目と 3 番目の選挙運動の計画を実行するのが最善である．

入力例 2

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

出力例 2

18

　この入力例は，小課題 3 の制約を満たす．

入力例 3

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

3

　この入力例は，小課題 4 の制約を満たす．

入力例 4

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

出力例 4

29191