CF48G.Galaxy Union

In a far away galaxy there are n inhabited planets numbered with numbers from 1 to n. One day the presidents of all the n planets independently from each other came up with an idea of creating the Galaxy Union. Now they need to share this wonderful idea with their galaxymates, that’s why each president is busy working out a project of negotiating with the other presidents.

For negotiations between some pairs of the planets there are bidirectional communication channels, each of which is characterized with "dial duration" t__i which, as a rule, takes several hours and exceeds the call duration greatly. Overall the galaxy has n communication channels and they unite all the planets into a uniform network. That means that it is possible to phone to any planet v from any planet u, perhaps, using some transitional planets _v_1, _v_2, ..., v__m via the existing channels between u and _v_1, _v_1 and _v_2, ..., v__m - 1 and v__m, v__m and v. At that the dial duration from u to v will be equal to the sum of dial durations of the used channels.

So, every president has to talk one by one to the presidents of all the rest n - 1 planets. At that the negotiations take place strictly consecutively, and until the negotiations with a planet stop, the dial to another one does not begin. As the matter is urgent, from the different ways to call the needed planet every time the quickest one is chosen. Little time is needed to assure another president on the importance of the Galaxy Union, that’s why the duration of the negotiations with each planet can be considered equal to the dial duration time for those planets. As the presidents know nothing about each other’s plans, they do not take into consideration the possibility that, for example, the sought president may call himself or already know about the founding of the Galaxy Union from other sources.

The governments of all the n planets asked you to work out the negotiation plans. First you are to find out for every president how much time his supposed negotiations will take.

在遥远的银河系中，有 $n$ 颗有人居住的行星，编号为 $1$ 到 $n$。某天，这 $n$ 颗行星的总统各自独立地萌生了一个绝妙的想法：成立“银河联盟”。现在他们需要将这一美好构想传达给各自的银河同胞，因此每位总统都在紧张地制定与其余总统进行协商的方案。

某些行星对之间存在双向通信信道，每条信道具有一个“拨号时长” $t_i$；该时长通常长达数小时，且远大于实际通话时间。整个银河系共有 $n$ 条通信信道，它们将所有行星连接成一个连通网络。这意味着：对于任意两颗行星 $u$ 和 $v$，总存在一条路径（可能经过若干中转行星 $v_1, v_2, \dots, v_m$），使得可通过信道 $u \leftrightarrow v_1$、$v_1 \leftrightarrow v_2$、…、$v_{m-1} \leftrightarrow v_m$、$v_m \leftrightarrow v$ 从 $u$ 拨号至 $v$。此时，从 $u$ 到 $v$ 的总拨号时长即为所经各信道拨号时长之和。

因此，每位总统需依次与其他 $n-1$ 颗行星的总统逐一协商。协商严格按顺序进行：只有当前与某颗行星的协商完全结束，才开始拨号联系下一颗行星。由于事态紧急，每次联络目标行星时，均选择拨号时长最短的路径。向另一位总统阐明银河联盟的重要性所需时间极短，因此可认为与每一颗行星协商的耗时即等于该路径的拨号时长。又因各位总统互不知晓彼此计划，故不考虑例如“目标总统可能已自行发起联络”或“已通过其他渠道获知银河联盟成立”等情形。

所有 $n$ 颗行星的政府委托你制定协商方案。首先，你需要为每位总统计算出其全部协商预计所需的总时间。

The first line contains an integer n (3 ≤ n ≤ 200000) which represents the number of planets in the Galaxy and the number of communication channels equal to it. The next n lines contain three integers each a__i, b__i and t__i (1 ≤ a__i, b__i ≤ n, a__i ≠ b__i, 1 ≤ t__i ≤ 103) that represent the numbers of planet joined by a communication channel and its "dial duration". There can be no more than one communication channel between a pair of planets.

第一行包含一个整数 $n$（$3 \leq n \leq 200000$），表示银河系中的行星数量，同时也等于通信信道的数量。接下来的 $n$ 行每行包含三个整数 $a_i$、$b_i$ 和 $t_i$（$1 \leq a_i, b_i \leq n$，$a_i \neq b_i$，$1 \leq t_i \leq 10^3$），分别表示由一条通信信道连接的两颗行星的编号及其“拨号时长”。任意两颗行星之间至多存在一条通信信道。

In the first line output n integers — the durations of the supposed negotiations for each president. Separate the numbers by spaces.

在第一行输出 n 个整数——每位总统假定的谈判持续时间。数字之间用空格分隔。