Restaurant recommendation

The KOI country has $N$ cities, numbered 1 through $N$.

The road network of KOI country is a tree when cities are vertices and roads are bidirectional edges. A tree is a connected graph with no cycles.

There are $M$ restaurants in total, numbered 1 through $M$. Some cities may have no restaurant, and some cities may have two or more.

Restaurant $i$ ($1 \le i \le M$) is in city $c_i$, has delivery range $d_i$, and has customer preference $g_i$. Restaurant $i$ can deliver only to cities reachable from city $c_i$ within $d_i$ roads or fewer. Let $R_i = \{j \mid d(c_i, j) \le d_i\}$ be the set of cities restaurant $i$ can deliver to, where $d(a, b)$ is the length of the shortest path between cities $a$ and $b$, that is, the minimum number of roads to cross between them.

You operate a delivery app. To avoid overlapping service, you want to choose a set $S$ of restaurants from the $M$ restaurants such that no city belongs to the delivery sets of two or more restaurants in $S$. That is, for any two different restaurants $i$ and $j$ in $S$, $R_i \cap R_j = \emptyset$.

Among all valid sets $S$, find the one with the largest total preference and print that total.

The first line contains two integers $N$ and $M$, separated by a space.

Each of the next $N-1$ lines contains two integers $a$ and $b$, separated by a space, meaning there is a road between cities $a$ and $b$.

Each of the next $M$ lines contains three integers $c_i$, $d_i$, and $g_i$, separated by spaces, giving the city, delivery range, and preference of restaurant $i$ ($1 \le i \le M$).

Print on the first line the largest total preference of a valid set $S$.

• All input values are integers.
• $1 \le N \le 10^5$
• $1 \le M \le 10^5$
• For every $i$ ($1 \le i \le M$): $0 \le d_i \le N - 1$, $1 \le g_i \le 10^9$