在“困惑之州”（State of Confusion）有 $n$ 个城市，编号为 $1$ 到 $n$。有 $n$ 条双向道路连接这些城市。第 $i$ 条道路连接城市 $a_i$ 和 $b_i$，长度为 $d_i$ 英里。

所有 $n$ 个城市都是连通的。换句话说，无论你从哪个城市出发，总是可以通过给定的道路到达任何其他城市。此外，没有道路将一个城市与自身相连，且任意两个城市之间最多只有一条道路。

你希望在其中一个城市举办一场全州范围的活动。需要考虑的重要因素之一是，其他城市距离活动举办地有多远。两个城市之间的距离是连接它们的最短路径的长度。

给定所有道路的信息，求出从该州的每个城市出发，到距离其最远的城市的距离。

输入格式

输入的第一行包含一个整数 $n$（$3 \le n \le 3 \cdot 10^5$），表示该州的城市数量。

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

输出格式

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

样例

输入样例 1

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

输出样例 1

4 5 3 5