P10602 [CEOI 2009] Harbingers

给定一颗树，树中每个结点有一个邮递员，每个邮递员要沿着唯一的路径走向 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 的最少时间。

对于 $20\%$ 的数据，$N\leq 2500$； 对于 $50\%$ 的数据，树是一条链； 对于所有数据，$3\leq N\leq 10^5$，$0\leq W_i,V_i\leq 10^9$，每条边长度不超过 $10^4$。