Migrated from Lutece 2998 Ants Tree

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$ 个节点，每个节点上有一只蚂蚁。我们定义这棵树的根节点为 $1$ 号节点。每一只蚂蚁身上都携带了一些信息，而这些蚂蚁为了将信息传到根节点上，他们会在出发前花费 $t_i$ 的时间准备，然后以 $v_i$ 的速度不断的向根节点移动。

然而蚁群中间出现了懒狗，一些蚂蚁会在向上移动的过程中将信息丢给位于处在这个节点上的蚂蚁，让这个节点上的蚂蚁帮忙代传。

位于根节点的蚁后想知道，当第 $i$ 个节点上的蚂蚁从 $0$ 时刻出发，其他蚂蚁在未接到第 $i$ 只蚂蚁委托时不会移动的情况下（也即同一时间最多只会有一只蚂蚁在移动），她最快能在什么时候接收到第 $i$ 个节点上的信息。

Input

第一行一个整数 $n$ ，表示树上节点的个数。

接下来 $n-1$ 行，每行三个整数 $x_i,y_i,z_i$ 表示节点 $x_i,y_i$ 之间有一条长度为 $w_i$ 的边。

接下来 $n$ 行，每行两个整数 $t_i,v_i$，表示第 $i$ 只蚂蚁的速度和准备时间。其中速度的含义是 每走1单位距离需要花费 $v_i$ 的时间。

Output

输出 $1$ 行 $n$ 个整数，表示蚂蚁从 $i$ 号节点出发到达 $1$ 号节点所需要的最短时间。

Samples

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

0 206 321 542 328

Constraints

$1\leq n \leq 10^{5}, 1\leq w_i,v_i,t_i\leq 10^{9}, 1 \leq x_i, y_i \leq n$，保证数据最后形成的是一棵树。

Resources

2023 UESTC ICPC Training for Search and Dynamic Programming