题目描述

“迷惑州”有 $n$ 座城市，编号为 $1$ 到 $n$，并有 $n$ 条连接城市的双向道路。第 $i$ 条道路连接城市 $a_i$ 和 $b_i$，长度为 $d_i$ 英里。

所有 $n$ 座城市彼此连通。也就是说，无论从哪座城市出发，都一定能通过给出的道路到达其他任意城市。此外，没有道路连接一座城市与其自身，任意两座城市之间至多有一条道路。

你打算选择其中一座城市举办全州活动。需要考虑的一个重要因素，是其余城市距离活动举办地有多远。两座城市之间的距离定义为连接它们的最短路径长度。

给定所有道路的信息，求从州内每一座城市出发，到距它最远城市的距离。

输入格式

第一行包含一个整数 $n$（$3\le n\le3\cdot10^5$），表示城市数量。

接下来 $n$ 行，每行包含三个整数 $a_i,b_i,d_i$（$1\le d_i\le10^7$），描述一条道路。

输出格式

在一行输出 $n$ 个整数，其中第 $i$ 个数表示从城市 $i$ 到距它最远城市的距离。

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

4 5 3 5