E. Mine Evacuation
time limit per test
3 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

There are $$$n$$$ mining sites and $$$m$$$ bidirectional pipes. The sites are numbered from $$$1$$$ to $$$n$$$. Site $$$i$$$ has elevation $$$h_i$$$, worker count $$$p_i$$$, and evacuation capacity $$$c_i$$$.

You must choose a nonnegative integer water level $$$h$$$. Every site with $$$h_i\le h$$$ and every pipe incident to such a site are deleted, and workers at deleted sites cannot evacuate. The remaining sites and pipes form connected components.

For each connected component, let its total worker count be $$$s_p$$$ and its total evacuation capacity be $$$s_c$$$. If $$$s_p\le s_c$$$, all $$$s_p$$$ workers in that component evacuate successfully; otherwise, evacuation fails for the entire component and none of its workers evacuate.

You may choose the water level freely. Find the maximum number of workers that can evacuate.

Input

There is only one test case in each test file.

The first line contains two integers $$$n$$$ and $$$m$$$ ($$$1\le n\le2\cdot10^5$$$, $$$0\le m\le2\cdot10^5$$$).

The $$$i$$$-th of the next $$$n$$$ lines contains three integers $$$h_i$$$, $$$p_i$$$, $$$c_i$$$ ($$$1\le h_i\le10^9$$$, $$$0\le p_i,c_i\le10^9$$$). Different sites may have the same elevation.

Each of the next $$$m$$$ lines contains two integers $$$u$$$ and $$$v$$$ ($$$1\le u,v\le n$$$, $$$u\ne v$$$), describing a bidirectional pipe between these sites. There are no multiple edges or self-loops.

Output

Print one integer: the maximum total number of workers that can evacuate.

Examples
Input
4 3
1 100 0
3 10 50
5 30 10
7 5 10
1 2
2 3
3 4
Output
45
Input
5 5
6 3 5
2 8 2
9 5 6
4 4 1
6 2 4
1 2
2 3
2 4
3 5
4 5
Output
14
Note

Figure: Components and evacuation results at different water levels

In the first example, with $$$h=0$$$, the only component has $$$145$$$ workers and capacity $$$70$$$, so none evacuate. With $$$h=2$$$, the remaining sites have $$$45$$$ workers and capacity $$$70$$$, so all evacuate. With $$$h=4$$$, the remaining component has $$$35$$$ workers and capacity $$$20$$$, so none evacuate. With $$$h=6$$$, only site $$$4$$$ remains and $$$5$$$ workers evacuate. The maximum is $$$45$$$.

In the second example, choosing $$$h=2$$$ leaves site $$$1$$$ as one component, with $$$3$$$ workers and capacity $$$5$$$. Sites $$$3,4,5$$$ form another component, with $$$11$$$ workers and capacity $$$11$$$. The maximum number of workers evacuated is therefore $$$14$$$.