TLE '16 Contest 1 P5 - Battle Plan

View as PDF

Submit solution


Points: 17 (partial)
Time limit: 1.0s
Memory limit: 128M

Author:
Problem types
Allowed languages
Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, CommonLisp, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, Nim, ObjC, OCaml, Octave, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig

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

Subtask 1 [10%]

2 \leq N \leq 10

Subtask 2 [20%]

2 \leq N \leq 2\,000

Subtask 3 [70%]

2 \leq N \leq 100\,000

In all cases:

1 \leq c_i \leq 100\,000

1 \leq d_i \leq 100\,000

1 \leq p_i \leq N

Input Specification

The first line will contain a single integer, N.

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

Output Specification

The output will consist of N-1 lines. The i^{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

Comments

There are no comments at the moment.