哈哈哈哈！！！你的宿敌，那位风度翩翩的间谍 Waco Powers，终于落入了你秘密火山基地的死亡陷阱（或者你是这么认为的，毕竟你当时太忙了，没能亲眼见证）。终于，你准备好征服世界了！

没有什么能阻挡你！好吧，除了一个小小的后勤问题。你的邪恶军队宣布，如果不给钱，他们就不会继续在这些弱小的国家中进行无情的破坏。不幸的是，你的现金不足——火山巢穴有很多优点，但“经济实惠”绝对不是其中之一。你不得不从差旅预算中挪用资金来支付你那些不知感恩的下属。现在，你还不确定该如何将你的军队部署到位以征服世界。

你拥有一张世界各国地图以及所有可用的运输路线。每条路线连接两个国家，并且每支通过该路线的军队都有固定的通行成本。这些路线的布局使得任意两个国家之间只有一条路径。你知道每支军队目前的位置，以及为了征服世界，你需要永久驻扎在每个国家的军队数量。你该如何以尽可能低的成本将军队调动到位，从而征服世界？

输入格式

输入的第一行包含一个整数 $n$ ($1 \le n \le 250\,000$)，表示国家的数量。接下来有 $n - 1$ 行，每行包含三个整数 $u, v$ 和 $c$ ($1 \le u, v \le n, 1 \le c \le 10^6$)，表示连接国家 $u$ 和 $v$ 的双向路线，每支军队通过该路线的成本为 $c$。

最后有 $n$ 行，第 $i$ 行包含两个非负整数 $x_i$ 和 $y_i$，表示目前在国家 $i$ 有 $x_i$ 支军队，而你最终需要在该国家至少部署 $y_i$ 支军队。军队总数（所有 $x_i$ 之和）至少等于所有 $y_i$ 之和，且不超过 $10^6$。

输出格式

输出将军队调动到位使得所有国家 $i$ 至少拥有 $y_i$ 支军队的最小成本。

样例

输入 1

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

输出 1

15

输入 2

6
1 2 2
1 3 5
1 4 1
2 5 5
2 6 1
0 0
1 0
2 1
2 1
0 1
0 1

输出 2

9