The package for this problem was not updated by the problem writer or Codeforces administration after we've upgraded the judging servers. To adjust the time limit constraint, a solution execution time will be multiplied by 2. For example, if your solution works for 400 ms on judging servers, then the value 800 ms will be displayed and used to determine the verdict.

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

dp

trees

two pointers

*2700

No tag edit access

The problem statement has recently been changed. View the changes.

×
G. Galaxy Union

time limit per test

3 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputIn 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.

Input

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} ≤ 10^{3}) 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.

Output

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

Examples

Input

3

1 2 3

2 3 2

1 3 1

Output

4 5 3

Input

3

1 2 3

2 3 2

1 3 5

Output

8 5 7

Input

4

1 2 3

2 3 2

3 4 1

4 1 4

Output

12 8 8 8

Codeforces (c) Copyright 2010-2024 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Apr/15/2024 12:24:00 (g1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|