Fax McClad, Croneria's most strategic bounty hunter, is planning an attack against the infamous Dankey Kang! Fax needs to successfully command squadrons of Kyuwing starfighters from various planets in order to defeat the vicious Dankey Kang Gang!

There are ~N~ planets, numbered from ~1~ to ~N~, that are present today and Dankey Kang is hiding on planet ~N~. Each planet ~i~, excluding planet ~N~, has a single one-way path to ~p_i~, another planet in the system, with a length of ~d_i~ spacemiles. It is guaranteed that every planet can reach planet ~N~ using some sequence of paths.

However, the lack of money is always stopping Fax from accomplishing his goals. In particular, he needs to ensure that expenses due to fuel costs are minimal. Each planet ~i~, excluding planet ~N~, has a fuel cost ~c_i~, signifying the cost of one unit of fuel for one Kyuwing. One unit of fuel is only enough to travel one spacemile, but Kyuwings have very large fuel tanks and can thus hold infinite amounts of fuel.

The battle is starting! Please help Fax determine the minimal cost of fuel per Kyuwing starting from all planets from ~1~ to ~N-1~.

Constraints

For all subtasks:

~1 \le c_i, d_i \le 100\,000~

~1 \le p_i \le N~

Subtask 1 [10%]

~2 \le N \le 10~

Subtask 2 [20%]

~2 \le N \le 2\,000~

Subtask 3 [70%]

~2 \le N \le 100\,000~

Input Specification

The first line will contain a single integer, ~N~.

~N-1~ lines of input follow. The ~i^\text{th}~ line will contain three space-separated integers, ~p_i~, ~d_i~, and ~c_i~.

Output Specification

The output will consist of ~N-1~ lines. The ~i^\text{th}~ line should contain a single integer specifying the minimal fuel cost for a single Kyuwing starfighter starting from planet ~i~ travelling to planet ~N~.

Sample Input

4
3 1 3
3 2 8
4 1 7

Sample Output

6
23
7