34785번 - Farthest City 다국어

문제

There are $n$ cities in the State of Confusion, numbered from 1ドル$ to $n$. There are $n$ bidirectional roads that connect the cities. The $i$^th road connects cities $a_i$ and $b_i,ドル and is $d_i$ miles long.

All $n$ cities are connected. In other words, regardless of which city you start from, it is always possible to reach any other city using the given roads. In addition, no road connects a city to itself, and there is at most one road between any pair of cities.

You are interested in holding a statewide event in one of the cities. One of the important factors to consider is how far away the rest of the cities are from where the event will be held. The distance between two cities is the length of the shortest path that connects them.

Given the information about all roads, find the distance to the farthest city from every city in the state.

입력

The first line of the input contains a single integer $n$ (3ドル \le n \le 3 \cdot 10^5$), representing the number of cities in the state. Each of the next $n$ lines contains three integers $a_i,ドル $b_i,ドル $d_i$ (1ドル \le d_i \le 10^7$), describing one of the roads.

출력

Output $n$ integers on a single line, where the $i$^th number denotes the distance of the city that is the farthest from city $i$.

제한

노트