在一个遥远的星系里,有n颗有人居住的行星,编号为1到n。有一天,n 个行星的总统各自独立地提出了创建银河联盟的想法。现在他们需要与他们的银河伙伴分享这个美妙的想法,这就是为什么每位总统都忙于制定与其他总统谈判的项目。
对于某些行星对之间的谈判,存在双向通信通道,每个通道都以“拨号持续时间”ti 为特征,通常需要几个小时并且大大超过通话持续时间。总的来说,银河系有 n 个通信通道,它们将所有行星联合成一个统一的网络。这意味着可以通过 u 和 v1、v1 和 v2、...、vm - 1 和 vm、vm 和 v 之间的现有通道使用一些过渡行星 v1、v2、...、vm 从任何行星 u 向任何行星 v 打电话。此时,从 u 到 v 的拨号持续时间将等于所使用通道的拨号持续时间之和。
所以,每位总统都必须与其余n-1个行星的总统一一交谈。此时,谈判严格连续进行,直到与一个行星的谈判停止为止,才开始向另一个行星进行谈判。由于事情紧急,从不同的方式呼叫所需的星球,每次都选择最快的。需要很少的时间来向另一位总统保证银河联盟的重要性,这就是为什么与每个行星谈判的持续时间可以被认为等于这些行星的表盘持续时间。由于总统们对彼此的计划一无所知,他们没有考虑到这样的可能性,例如,被寻求的总统可能会自称或已经从其他来源知道银河联盟的成立。
n个星球的政府要求你制定谈判计划。首先,你要找出每位总统的所谓谈判需要多长时间。
输入
第一行包含一个整数n (3 ≤ n ≤ 200000),它代表银河系中行星的数量以及与其相等的通信通道的数量。接下来的 n 行包含三个整数,每个 ai、bi 和 ti(1 ≤ ai,bi ≤ n,ai ≠ bi,1 ≤ ti ≤ 103),表示通过通信通道连接的行星数量及其“拨号持续时间”。一对行星之间只能有一个通讯渠道。
输出
在第一行输出 n 个整数——每位总统的假定谈判持续时间。用空格分隔数字。
示例
输入 #1
3 1 2 3 2 3 2 1 3 1
输出 #1
4 5 3
输入 #2
3 1 2 3 2 3 2 1 3 5
输出 #2
8 5 7
输入 #3
4 1 2 3 2 3 2 3 4 1 4 1 4
输出 #3
12 8 8 8