Intelligence Agency Setup

In recent years, conflicts have erupted between Country C and Country D. Recently, Country C infiltrated a city in Country D, which can be modeled as a tree with $$n$$ nodes and $$n-1$$ edges, where any two nodes are connected by a unique path.

Country C has $$m$$ proposals for setting up intelligence agencies. The $$i$$-th proposal places agents along every edge on the shortest path between nodes $$x_i$$ and $$y_i$$ at a cost of $$v_i$$. Each edge in the tree is assigned an intelligence value $$c_i$$, representing the revenue gained by collecting intelligence on that edge. Note that if an edge is covered by both proposals, its revenue is only counted once.

Due to limited manpower, only two proposals can be implemented. In order for the agencies to cooperate effectively, the two chosen proposals must have at least one common edge in their coverage. Let the total revenue be the sum of the intelligence values of all edges covered (counted once per edge even if covered by both proposals) and the total cost be the sum of the costs of the two proposals. The goal is to maximize the difference:

$$\text{Difference} = (\text{Total Revenue}) - (\text{Total Cost}). $$

If no two proposals share a common edge, output F. Note that the answer may be negative.

inputFormat

The input begins with two integers $$n$$ and $$m$$ (number of nodes and number of proposals).

Then follow $$n-1$$ lines, each containing three integers u v c indicating an undirected edge between nodes u and v with intelligence value c.

Then follow $$m$$ lines, each containing three integers x y v representing a proposal that covers the shortest path between nodes x and y with a cost of v.

outputFormat

Output a single value: the maximum difference (total revenue minus total cost) achievable by choosing two proposals whose coverage has at least one common edge. If there is no valid pair of proposals, output F.

sample

4 3
1 2 3
2 3 5
2 4 2
1 3 4
3 4 1
1 4 3

6