Little X has a tree consisting of n nodes (they are numbered from 1 to n ). Each edge of the tree has a positive length. Let's define the distance between two nodes v and u (we'll denote it d(v, u)) as the sum of the lengths of edges in the shortest path between v and u . A permutation p is a sequence of n distinct integers p 1, p 2, ..., p n (1 ≤ p i ≤ n). Little X wants to find a permutation p such that sum is maximal possible. If there are multiple optimal permutations, he wants to find the lexicographically smallest one. Help him with the task!

输入描述:

The first line contains an integer n (1 ≤ n ≤ 105).Each of the next n - 1 lines contains three space separated integers ui, vi, wi (1 ≤ ui, vi ≤ n; 1 ≤ wi ≤ 105), denoting an edge between nodes ui and vi with length equal to wi.It is guaranteed that these edges form a tree.

输出描述:

In the first line print the maximum possible value of the described sum. In the second line print n integers, representing the lexicographically smallest permutation.