#215895. [JOI Open 2015] Election Campaign

In the Republic of JOI, there are cities numbered from 1 to . The cities are connected with roads. People in the Republic of JOI are travelling between cities using these roads. They can pass each of the roads in both directions. They can travel between any two cities by passing through one or several roads.

Mr. IOI is a candidate for the president of the Republic of JOI. Of course, to become the president, he must perform the campaign for the presidential election. His secretary made plans for the election campaign. In the -th plan, Mr. IOI will travel from the city to the city passing through minimum number of roads, and make a public speech in each of the cities on the way (including the city and the city ). Because his secretary is brilliant, it is known that Mr. IOI will get votes if the -th plan is performed. It is possible to perform several plans.

However, people in the Republic of JOI are impatient. If Mr. IOI makes public speeches more than once in the same city, he will lose the support from people in the Republic of JOI.

Because Mr. IOI would like to become the president, he wants to get as many votes as possible. Since you are a superprogrammer in the Republic of JOI, he asked you to write a program which calculates the maximum number of votes Mr. IOI can get in the presidential election under the assumption that he will not make public speeches more than once in the same city.

Task

Given the number of cities in the Republic of JOI, the information on the roads, the number of plans for the election campaign, and information of each plan, write a program which calculates the maximum number of votes Mr. IOI can get in the presidential election.

Read the following data from the standard input.

• The first line of input contains an integer , the number of cities in the Republic of JOI.
• The -th line () of the following lines contains two space separated integers . This means the -th road connects the city and the city .
• The following one line contains an integer , the number of plans for the election campaign.
• The -th line () of the following lines contains three space separated integers . This means, in the -th plan, Mr. IOI will travel from the city to the city passing through minimum number of roads, and he will get votes if this plan is performed.

The output should consist of one line, and contain one integer which denotes the maximum number of votes Mr. IOI can get in the presidential election.

样例输入 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

样例输入 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

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

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

Sample 1 Explanation

In this sample input, the optimal strategy is to perform the plan 1 and the plan 3 for the election campaign.

Sample 2 Explanation

This sample input satisfies the constraints of the subtask 3.

Sample 3 Explanation

This sample input satisfies the constraints of the subtask 4.

Constraints

All input data satisfy the following conditions.

• .
• .
• .
• ().
• People can travel between any two cities by passing through one or several roads.
• .
• .
• .
• ().
• .

Subtask

Subtask 1 [10 points]

• .

Subtask 2 [5 points]

• ().
• ().
• ().

Subtask 3 [5 points]

• ().
• ().

Subtask 4 [30 points]

• ().

Subtask 5 [10 points]

• .
• .

Subtask 6 [40 points]

There are no additional constraints.