Cover the Paths

题目描述

You are given a rooted tree with $n$ vertices. The root is vertex $1$.

You are also given $m$ paths. The $i$-th path is described by two vertices $a_i$ and $b_i$ and an integer $c_i$; it consists of all edges on the simple path between $a_i$ and $b_i$. It is guaranteed that $a_i$ is an ancestor of $b_i$, or $b_i$ is an ancestor of $a_i$.

You may place markers on the edges of the tree. Each edge can hold any number of markers. For each $i$, at least $c_i$ of the placed markers must lie on the edges of the $i$-th path.

Find the minimum total number of markers you need to place.

输入格式

The first line contains $n$ and $m$.

Each of the next $n-1$ lines contains $u$ and $v$ ($1 \le u, v \le n$, $u \ne v$) — an edge of the tree.

Each of the next $m$ lines contains $a_i$, $b_i$, $c_i$ ($1 \le a_i, b_i \le n$, $a_i \ne b_i$, $1 \le c_i \le 10^9$); it is guaranteed that $a_i$ is an ancestor of $b_i$, or $b_i$ is an ancestor of $a_i$.

$2 \le n \le 10^5$, $1 \le m \le 10^5$.

输出格式

Print a single integer — the minimum total number of markers.

样例输入 #1

2 1
1 2
1 2 6

样例输出 #1

6

样例输入 #2

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

样例输出 #2

3