beecrowd | 3115

Roads

By Giovanna Kobus Conrado, University of São Paulo BR Brazil

Timelimit: 1

Tland is a very beautiful country. It consists of N cities connected by N-1 bidirectional roads in such a way that there is a path from every city to very other city. Because of a storm the capitol is currently facing a really heavy shortage of food.

All the other cities offered to send a truck full of food to help, but there is one problem: each of the roads in Tland can only handle so much weight at a time.

So now the government of Tland wants to know: for each city in Tland what is the heaviest truck they can send to the capitol such that it does not exceed the weight limit for any road it will have to go through.

Input

The first line of input consists of an integer N, the number of cities in Tland (1≤N≤105).

The following N-1 lines each consist of three integers: V, U and C, that indicate that there is a road from city V, to city U that can handle trucks that weigh at most C quilograms (1≤V,UN and 1≤C≤109).

The capitol will always be the city represented with N.

Output

The output must be a line containing N-1 integers: the i-th of them indicates the weight of the heaviest truck that city i can send to the capitol.

Input Sample Output Sample

5
3 5 3
2 4 1
3 2 4
1 4 1

1 3 3 1