K. The Demon Jester
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Playf has recently found joy in life in LOL: He falls in love with the Demon Jester.

At this time, Playf will fight against Malphite. They fight on a tree consisting of $$$n$$$ vertices numbered from $$$1$$$ to $$$n$$$. Malphite's initial position is vertex $$$1$$$, and Playf can choose any vertex as his initial position. The length of each edge on the tree is $$$1$$$, and both Playf and Malphite have a movement speed of $$$1$$$ per second. (At any moment, they can choose to move in any direction along the edge or stay still, even if they are on an edge at that time.)

Before the game starts, Playf has placed $$$m$$$ boxes in advance. The $$$i_{th}$$$ box is placed on the vertex $$$p_i$$$, with trigger range $$$a_i$$$ and attack power $$$b_i$$$, which means that if Malphite reaches any vertex that satisfies $$$dis(x , p_i) \lt = a_i$$$ ($$$dis(u,v)$$$ represents the shortest distance from $$$u$$$ to $$$v$$$), box $$$i$$$ will be triggered and deal $$$b_i$$$ damage to Malphite. Each box can only be triggered once, and the box will disappear after dealing damage.

Malphite has been carried away by anger, and will chase Playf along the shortest path by maximum speed all the time after the game starts. When Malphite's position coincides with Playf (which means that the distance between Malphite and playf is exactly $$$0$$$, no matter they meet on the vertex or on the edge), Playf will be killed by angry Malphite, ending his sinful life. Malphite will no longer move after Playf dies.

In the game, Playf has one chance to use the skill "Fraud Magic" (He can also choose not to use this skill during the game). Using this skill does not take time, it can help Playf teleport to any vertex on the tree, and this skill can be used at any moment.

Since Malphite is so Sturdy that he will not die during the game.

Now Playf wants to know the maximum amount of damage he can deal to Malphite during the game.

Input

The first line contains two integers $$$n, m(2 \le n\le 200\ 000,0\le m \le 200\ 000)$$$  — the number of vertices in the tree, and the number of boxes have been placed.

Each of the next $$$n-1$$$ lines contain a pair of numbers $$$u_i, v_i(1 \le u_i,v_i \le n)$$$  — an edge of the tree.

Each of the next $$$m$$$ lines contain three integers $$$p_i,a_i,b_i(2 \le p_i\le n, 0\le a_i \le n, 1 \le b_i \le 10^9)$$$  — the $$$i_{th}$$$ box's position, trigger range and attack power.

It is guaranteed that for each $$$1\le i\le m$$$, $$$dis(1, p_i) \gt a_i$$$.

Output

Print one integer in a line  — the maximum amount of damage Playf can deal to Malphite.

Examples
Input
4 2
1 2
1 3
3 4
4 0 2
2 0 1
Output
2
Input
4 2
1 2
1 3
3 4
4 1 2
2 0 1
Output
3
Input
2 3
1 2
2 0 1000000000
2 0 1000000000
2 0 1000000000
Output
3000000000