Tree Harvesting Problem

You are given a tree with n nodes numbered from 1 to n, with node 1 being the root. The tree has exactly n-1 edges. Additionally, there are m fruits. The j-th fruit grows at node \(v_j\), matures exactly on day \(d_j\), and yields \(w_j\) juice when harvested. A fruit can only be collected on its maturity day.

The only way to harvest fruit is to cut one edge of the tree. When you cut an edge that connects a parent and a child, you disconnect the subtree rooted at the child. On that same day, you harvest all fruits in the detached subtree whose maturity day is equal to the day you performed the cut. Once an edge is cut, no further harvests may be obtained from that detached subtree (even if some fruits in it mature later).

Your task is to choose a set of edges to cut (each cut is performed on the corresponding maturity day you select for that cut) so that no two cuts occur on the same root-to-leaf path (since once a subtree is detached, you cannot later cut an edge in it) and thereby maximize the total amount of juice harvested.

More formally, when you cut an edge from a node u to its child v on day \(d\), you obtain a reward equal to \(\sum_{x \in T_v}\, [d_x = d] \cdot w_x\) (where \(T_v\) is the entire subtree rooted at v, and \([P]\) is 1 if proposition P holds and 0 otherwise). Alternatively, you may choose not to cut an edge so that you have the opportunity to harvest fruit from lower parts of the tree by cutting deeper edges.

Calculate the maximum total amount of juice you can obtain.

Note: Fruit at the root cannot be harvested because there is no edge that disconnects the root from the tree.

inputFormat

The first line contains two integers \(n\) and \(m\) (\(2 \leq n \leq 10^5\) and \(1 \leq m \leq 10^5\)), representing the number of nodes in the tree and the number of fruits respectively.

The next \(n-1\) lines each contain two integers \(u\) and \(v\), meaning there is an edge between nodes \(u\) and \(v\). It is guaranteed that these edges form a tree with node 1 as the root.

The following \(m\) lines each contain three integers \(v_j\), \(d_j\), and \(w_j\) (\(1 \leq v_j \leq n\), \(1 \leq d_j \leq 10^9\) and \(1 \leq w_j \leq 10^9\)), describing that a fruit grows at node \(v_j\), matures on day \(d_j\), and yields \(w_j\) juice on harvesting.

outputFormat

Output a single integer, the maximum total juice that can be collected.

sample

3 2
1 2
1 3
2 2 5
3 1 10

15