Migrated from Lutece 2572 外交访问

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

有 $n$ 个国家通过 $n-1$ 条路径连接，为方便描述，我们对这些国家从 $1$ 到 $n$ 进行编号。每个国家都有一种特有的骏马，第 $i$ 号国家的马速度为 $v_i$，表示跑一公里需要花 $v_i$ 分钟。

现在除 $1$ 号国家以外的其他国家打算派出使者去 $1$ 号国家交流访问。每个国家的使者会选择一条距离最短的路线骑马前往 $1$ 号国家，出发时各国使者都是骑着本国的马。当使者经过一个国家，他可以选择继续往前走，或者选择停下来用当前的马匹去交换该国的马匹，具体地说，当使者经过第 $j$ 号国家，可以花 $w_j$ 分钟更换马匹，之后行进速度变为 $v_j$。

你想知道，第 $2$ 号至第 $n$ 号国家的使者到达 $1$ 号国家需要的最短时间。

Input

第一行输入一个正整数 $n$，表示国家的数量。 接下来 $n-1$ 行，每行输入三个正整数 $u,v,c$，表示有一条路径连接第 $u$ 号国家和第 $v$ 号国家，长度为 $c$ 公里。 接下来 $n$ 行，每行输入一对整数。第 $i$ 对整数 $w_i,v_i$ 分别表示在第 $i$ 号国家更换马匹需要的时间，以及第 $i$ 号国家马匹的速度。

Output

输出共 $n-1$ 行，每行输出一个整数。第 $i$ 行的值表示第 $i+1$ 号国家的使者到达第 $1$ 号国家所需的最短时间。

Samples

6
1 2 10
1 3 20
3 4 30
3 5 40
5 6 50
10 10
10 5
100 1
2 2
20 20
200 200

50
20
100
920
10940

Constraints

$2\leq n\leq 10^5$， $1\leq c\leq 10^4$， $0\leq w_i\leq 10^9$， $1\leq v_i\leq 10^9$ 数据保证每个国家的使者都能到达 $1$ 号国家。

Resources

2021 UESTC ICPC Training for Dynamic Programming