In the county of squirrels, there are N trees, and there are N−1 paths connecting some pairs of trees so that from any tree, you can reach any other tree by a sequence of paths. If we number all the paths from 1 to N−1 and all the trees from 1 to N, then the i-th path is trodden between trees u_i and v_i and has a length of l_i meters.

The squirrel Vadim is looking for a place to store supplies for the winter. This needs to be done in such a way that no other squirrel from the county can find these supplies. To do this, Vadim came up with a simple strategy to shake off any curious relatives without running too much himself. He will start at an arbitrary tree, then evaluate the lengths of all the paths leading from this tree and will run along the shortest one. Upon reaching the next tree, he will repeat this operation, excluding trees he has already visited that day. Vadim will continue this action until he arrives at a tree from which all paths lead to trees he has already visited. In the hollow of this tree, Vadim will set up his “warehouse.”

The squirrel Nastya has learned about Vadim’s strategy, and she needs to find out which tree Vadim will hide his supplies in. Unfortunately, she does not know which tree Vadim started his journey from. Help Nastya find the corresponding tree for each of the trees in the county.

The first line contains an integer N — the number of trees in the county of squirrels (2 ≤ N ≤ 10⁵).

In the following N−1 lines, there are three integers u_i, v_i, and l_i — the numbers of the trees connected by the i-th path and its length (1 ≤ u_i, v_i ≤ N, u_i ≠ v_i, 1 ≤ l_i ≤ 10⁹). It is guaranteed that the lengths of all paths are distinct.

Output N integers f_i — the number of the tree where Vadim’s “warehouse” is located if he started near the i-th tree.