该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

代送一封（mail）

题目描述

村里的临时邮站设在 $1$ 号地点，Y 同学今天要去若干地点送信。共有 $n$ 个地点和 $n-1$ 条双向道路，任意两个地点之间恰有一条简单路径。每经过一条道路，都要支付这条道路对应的运输费；同一条道路经过几次，就支付几次。

有 $m$ 封信，分别送往互不相同的地点 $v_1,v_2,\ldots,v_m$。Y 同学从 $1$ 号地点出发，途中到达一个目的地就可以送达对应的信，送完后可以在任意地点结束行程，不必返回邮站。携带信件的数量没有限制。

出发前，他还可以把其中至多一封信交给代送员。代送第 $i$ 封信需要支付 $c_i$ 的费用，此后 Y 同学就不必为了这封信到达 $v_i$；不过他仍然可以经过那里。求所有信都送达时，Y 同学支付的道路运输费与代送费之和的最小值。

输入格式

第一行包含两个整数 $n,m$。

接下来 $n-1$ 行，每行包含三个整数 $u,v,w$，表示地点 $u,v$ 之间有一条双向道路，每经过一次需要支付 $w$ 的运输费。

接下来 $m$ 行，第 $i$ 行包含两个整数 $v_i,c_i$，表示第 $i$ 封信的目的地和代送报价。

输出格式

输出一个整数，表示道路运输费与代送费之和的最小值。

样例

样例输入 #1

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

样例输出 #1

10

样例输入 #2

2 1
1 2 5
2 3

样例输出 #2

3

样例输入 #3

3 2
1 2 5
1 3 5
2 100
3 0

样例输出 #3

5

数据范围与约定

对于所有数据，保证 $2\le n\le2\times10^5$，$1\le m\le n-1$，$1\le u,v\le n$，$1\le w\le10^9$，$2\le v_i\le n$，$0\le c_i\le10^9$。所有 $v_i$ 两两不同，输入道路构成一棵树。

每个测试点 $5$ 分，分档如下：

特殊性质 A：道路恰好连接 $(1,2),(2,3),\ldots,(n-1,n)$。

特殊性质 B：每条道路的一端都是 $1$ 号地点。