Problem Description

C and D countries have been in conflict for years.

Recently, C successfully infiltrated a city in D. This city can be abstracted as an undirected graph with $n$ nodes connected by $n - 1$ bidirectional edges, forming a tree structure where any two nodes are reachable from each other.

Surprisingly, C's intelligence chief GGB discovered that this seemingly insignificant city is actually D's military center. Therefore, GGB decided to establish intelligence agencies within this city. After reconnaissance, intelligence expert TAC arranged $m$ plans for setting up these agencies. In the $i$-th plan, intelligence personnel are deployed along the shortest path from node $x_i$ to node $y_i$ with a cost of $v_i$ yuan.

However, due to a shortage of personnel, GGB can only implement two of these $m$ plans. TAC pointed out that for better cooperation between the two agencies, their intelligence-gathering ranges should share at least one common edge. To evaluate a plan's performance, GGB and TAC surveyed all edges, assigning each an intelligence value $c_i$, representing the revenue of $c_i$ yuan from gathering intelligence on that edge. Note that intelligence is unique, so when an edge's intelligence is collected by both agencies, it still only yields $c_i$ revenue.

Your task is to help GGB select two valid plans to implement, ensuring their intelligence-gathering ranges share at least one common edge, and maximizing the difference between the total revenue and the total cost.

Note that this value may be negative but is still valid. If no such two plans exist, output F.

Input Format

The input is read from the file center.in.

The first line contains an integer $T$, the number of test cases.

Each test case consists of $(n + m + 1)$ lines:

• The first line contains an integer $n$, the number of nodes in the city.
• Lines $2$ to $n$ contain three integers $a_i$, $b_i$, and $c_i$, representing a bidirectional edge connecting nodes $a_i$ and $b_i$ with an intelligence value of $c_i$, ensuring $a_i < b_i$ and $b_i$ are distinct.
• The $(n + 1)$-th line contains an integer $m$, the number of plans.
• Lines $(n + 2)$ to $(n + m + 1)$ contain three integers $x_i$, $y_i$, and $v_i$, representing the $i$-th plan to deploy intelligence personnel along the shortest path from node $x_i$ to node $y_i$ with a cost of $v_i$ yuan.

Output Format

The output is written to the file center.out.

The output contains $T$ lines.

For each test case, output one line: if a valid plan exists, output the maximum difference between the total revenue and the total cost; otherwise, output F.

Sample Input and Output

Input Sample #1

2
5
1 2 1
2 3 3
3 4 2
1 5 8
2
1 4 5
3 5 8
5
1 2 1
2 3 3
3 4 3
1 5 9
2
1 5 5
2 3 8

Output Sample #1

1
F

Input Sample #2

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

Output Sample #2

13

Notes/Hints

Sample 1 Explanation

This sample contains two test cases with the same city layout but different intelligence values and agency plans.

• For the first case, the shortest paths for the two plans are $1 \rightarrow 2 \rightarrow 3 \rightarrow 4$ and $3 \rightarrow 2 \rightarrow 1 \rightarrow 5$. The cost is $5 + 8 = 13$, and the revenue is $1 + 3 + 2 + 8 = 14$, resulting in a difference of $14 - 13 = 1$.
• For the second case, the shortest paths for the two plans are $1 \rightarrow 5$ and $2 \rightarrow 3$. These plans do not share a common edge, so it is invalid, and the output is F.

Sample 2 Explanation

Refer to the additional files center2.in and center2.ans for details.

Data Range

See the table in the original problem content for details on data ranges and special properties.

见题面 Input 部分

见题面 Output 部分