题目描述

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

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

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

输入格式

第一行一个正整数 $N$；

接下来 $N-1$ 行，每行三个正整数 $A,B,C$，表示结点 $A$ 和 $B$ 之间有一条长度为 $C$ 的边；

再接下来 $N-1$ 行，每行 $2$ 个整数 $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 2500$；

对于 $50\%$ 的数据，树是一条链；

对于所有数据，$3\leq N\leq 10^5$，$0\leq W_i,V_i\leq 10^9$，每条边长度不超过 $10^4$。