题目描述

给定一颗树，树中每个结点有一个邮递员，每个邮递员要沿着唯一的路径走向 capital（$1$ 号结点），每到一个城市他可以有两种选择：

1. 继续走到下个城市
2. 让这个城市的邮递员替他出发。

每个邮递员出发需要一个准备时间 $W_i$，他们的速度是 $V_i$，表示走一公里需要多少分钟。现在要你求出每个城市的邮递员到 capital 的最少时间（不一定是他自己到 capital，可以是别人帮他）？

输入格式

第一行一个整数 $N$。

以下 $N-1$ 行三个整数 $A,B,C$ 三个数表示 $A,B$ 之间有一条长为 $C$ 的边。

再N行每行两数 $W_i,V_i$。

输出格式

输出每个城市的邮递员到 capital 的最少时间。

样例

5
1 2 20
2 3 12
2 4 1
4 5 3
26 9
1 10
500 2
2 30

206 321 542 328

数据规模与约定

对于 $20\%$ 的数据：$N\leq 2.5\times10^3$。

对于 $50\%$ 的数据：数据为一条链。

对于 $100\%$ 的数据：$3\leq N\leq 10^5$，$0\leq W_i,V_i\leq 10^9$，每条道路长度不超过 $10^4$。

题目来源

Ceoi2009