题目描述

在一个遥远的星系中有 $n$ 颗有人居住的行星，编号从 $1$ 到 $n$。有一天，$n$ 颗行星上的领导人各自产生了建立同盟的想法。每个行星提出了创建星系同盟的想法，但是其他行星的人都不知道。现在他们需要与他们的星系伙伴分享这个绝妙的想法，这就是为什么每位领导人都忙于与其他领导人谈判。

某些行星之间的谈判有着双向通信通道，每个通道的都有 “拨号持续时间” $t_i$。通常，这需要几个小时并且大大超过了可供通话的时间。总的来说，银河系有 $n$ 条通信通道，它们将所有行星互相联系起来。这意味着可能从任意行星 $u$ 直接向任何行星 $v$ 打电话。或许可以使用一些中间行星 $v_1,v_2,\cdots,v_m$ 通过 $u$ 和 $v_1,v_2,\cdots,v_{m-1},v_m$ 和 $v$ 之间的现有通道。那么从 $u$ 到 $v$ 的拨号持续时间等于所使用通信通道的拨号持续时间之和。

所以，每个领导人都必须一个接一个地与所有其他 $n - 1$ 个行星的领导人交谈。谈判严格并连续进行，直到与一方的谈判结束后，另一颗行星的拨号才能开始。由于事情紧急，所以得以最快的方式与其他星球进行联络。几乎不需要时间向另一位总统保证银河联盟的重要性，这就是为什么与每个行星的谈判时间可以被视为等于这些行星的拨号持续时间。由于总统对彼此的计划一无所知，他们没有考虑到这样一种可能性：如被寻求的总统可能会自称或已经从其他来源知道银河联盟的成立。

$n$ 颗行星都要求你来制定谈判计划。你需要找出每位总统所谓的谈判需要多少时间。

输入格式

第一行输入一个整数 $n$（$3 \le n \le 2 \times 10 ^ {5}$），它代表星系中行星的数量和与之相等的通信信道的数量。

接下来 $n$ 行每行输入三个整数 $a_i, b_i$ 和 $t_i$（$1 \le a_i,b_i \le n$，$a_i \ne b_i$，$1 \le t \le 10 ^ {3}$），表示通过通信信道加入的行星数量及其“拨号持续时间”。一对行星之间不能超过一个通信通道。

输出格式

第一行输出 $n$ 个整数 —— 每位总统假定谈判的持续时间。

3
1 2 3
2 3 2
1 3 1

4 5 3

3
1 2 3
2 3 2
1 3 5

8 5 7

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

12 8 8 8