В графстве белок есть N деревьев, между N−1 парами деревьев протоптано по одной тропинке так, что от любого дерева можно добраться до любого другого по последовательности тропинок. Если пронумеровать все тропинки от 1 до N−1 и все деревья от 1 до N, то i-я тропинка протоптана между u_i-м и v_i-м деревьями и имеет длину l_i метров.

Белка Вадим ищет место для складирования припасов на зиму. Это нужно сделать так, чтобы никакая другая белка из графства не смогла найти эти запасы. Для этого Вадим придумал нехитрую стратегию, как избавиться от возможного хвоста из любопытных сородичей, но и самому слишком много не бегать. Он начнёт у произвольного дерева, затем оценит длину всех тропинок, которые ведут от этого дерева, и побежит по самой короткой. Прибежав к следующему дереву, он повторит эту операцию, но исключая деревья, около которых он уже был сегодня. Вадим будет повторять это действие до тех пор, пока он не прибежит к дереву, от которого все тропинки будут вести к уже посещённым ранее деревьям. В дупле этого дерева Вадим и устроит свой «склад».

Белка Настя прознала про эту стратегию Вадима, и ей необходимо узнать дерево, где Вадим будет прятать свои запасы. К сожалению, она не знает, около какого дерева начинал свои похождения Вадим. Помогите Насте найти соответствующее дерево для каждого из деревьев в графстве.

В первой строке даётся целое число N — количество деревьев в графстве белок (2 ≤ N ≤ 10⁵).

В следующих N−1 строках даются по три целых числа u_i, v_i и l_i — номера деревьев, которые соединяет i-я тропинка, и её длина (1 ≤ u_i, v_i ≤ N, u_i ≠ v_i, 1 ≤ l_i ≤ 10⁹). Гарантируется, что длины всех тропинок различные.

Выведите N целых чисел f_i — номер дерева, в котором находится «склад» Вадима, если он начинал около i-го дерева.