题目描述

李将军最近还有一个麻烦事，正好碰到了善于计算的叶书生。

函谷关是通往长安的重要旅游景点。

在李将军等名将的领导下，太平无忧，昔日的要塞已经变成了前往长安路上的必游之地。

为了淡化函谷关的军事感，新任工部侍郎欧阳微（字晓栋）决定将函谷关的道路染成紫色，在长安东侧，以取“紫气东来”之祥瑞。

函谷关道路系统可以看作一个树，规定根节点为停车场所在地，在停车场我们有若干台牛车。

每台牛车均从停车场出发，开到节点 $v$（该过程无需花费），然后付出 $c_i$ 的花费把结点 $v$ 到 $w$ 的道路染成紫色，该过程不重复经过同一节点。（可以理解为对于所有的 $v$ 与 $w$，都有 $v$ 是 $w$ 的祖先。）

虽然大唐很有钱，但是玄宗不愿浪费人民的劳动成果，他责令欧阳尚书选出花费最少的方案，使得所有的道路都被染成紫色。

欧阳尚书对李将军说：“你曾经也是驻守在这里的一名伍长，看你对这里有很深的感情，这个难题就交给你了。”

谁不知道欧阳尚书就是超级计算机的管理员啊！李将军无奈，找到了叶书生。

叶书生说：“其实我可以随时和超级计算机通信，但现在欧阳尚书从中作梗，这个问题怕是得你来了。”

李将军找到了你，并许诺你解出来之后可以去大唐东市喝 GoGo 奶茶，他买单。

输入格式

输入仅一组数据。

对于每一组数据，第一行包含两个整数 $n$ 和 $m$（$1 \leq n, m \leq 300000$），表示这棵树有 $n$ 个节点，共有 $m$ 辆牛车。

接下来的 $n-1$ 行中的每一行包含两个整数 $v_1$ 和 $v_2$，表示 $v_1$ 与 $v_2$ 联通。

接下来的 $m$ 行中的每一行包含三个整数 $w$、$v$ 和 $c$，表示第 $i$ 台牛车从停车场出发，先开到 $v$ 点，然后花费 $c$（$1 \leq c \leq 1000000000$）将 $v$ 到 $w$ 的道路染成紫色。

输出格式

对于每一组数据，输出仅一行，输出最小将所有道路染成紫色的花费。

样例输入

5 6
2 1
3 1
4 2
5 3
3 1 2
4 1 3
5 3 1
5 1 10
4 2 9
2 1 3

样例输出

6