Description

哇哈哈哈哈哈！！！你的宿敌，英俊的间谍 Waco Powers，终于在你的秘密火山基地的死亡陷阱中落败（或者你是这样假设的，因为你太忙了，没能亲眼目睹）。终于，你准备好征服世界了！

没有什么能阻挡你！嗯，除了一个小小的后勤问题。你的邪恶军队宣布，如果不支付报酬，他们将不会继续在世界上那些微不足道的国家中肆意破坏。不幸的是，你的现金快用完了——火山基地有很多优点，但“价格合理”不是其中之一。你不得不从旅行预算中抽出资金来支付你那些忘恩负义的下属。现在你不确定如何才能真正将你的军队部署到位以征服世界。

你有一张世界各国的地图，以及它们之间所有可用的运输路线。每条路线连接两个国家，并且每支军队使用它都有固定的费用。路线的布局使得在任何两个国家之间恰好有一条路径。你知道每支军队的当前位置，以及为了征服每个国家需要永久驻扎在那里的军队数量。你如何才能以最低的成本将军队部署到位，以便征服世界？

Input Format

输入的第一行包含一个整数 $n (1 \le n \le 250000)$，表示国家的数量。接下来是 $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}$。

Output Format

显示移动军队的最低成本，使得对于所有 $i$，国家 $i$ 至少有 $y_{i}$ 支军队。

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

15

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

9

Hint

时间限制：8 秒，内存限制：1024 MB。

题面翻译由 ChatGPT-4o 提供。