D. Дерево
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
stdin
вывод
stdout

У Little X есть дерево, состоящее из n вершин, пронумерованных от 1 до n. Для каждого ребра дерева задана его длина — целое положительное число. Определим расстояние между двумя вершинами v и u (обозначим его как d(v, u)) как сумму длин ребер в кратчайшем пути между v и u.

Будем называть перестановкой p последовательность из n различных целых чисел p1, p2, ..., pn (1 ≤ pi ≤ n). Little X хочет найти такую перестановку p, что сумма принимает как можно большее значение. При этом, если есть несколько оптимальных перестановок, он хочет найти лексикографически минимальную. Помогите ему найти такую перестановку!

Входные данные

В первой строке записано целое число n (1 ≤ n ≤ 105).

В каждой из следующих n - 1 строк записано три целых числа через пробел ui,  vi, wi (1 ≤  ui,  vi ≤  n; 1 ≤  wi ≤  105), обозначающих ребро между вершинами ui и vi с длиной, равной wi.

Гарантируется, что заданный граф является деревом.

Выходные данные

В первой строке выведите максимально возможное значение описанной суммы. Во второй строке выведите n целых чисел — искомая лексикографически минимальная перестановка.

Примеры
Входные данные
2
1 2 3
Выходные данные
6
2 1
Входные данные
5
1 2 2
1 3 3
2 4 4
2 5 5
Выходные данные
32
2 1 4 5 3