Description:
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 p1, p2, ..., pn (1 ≤ pi ≤ n). Little X wants to find a permutation p such that sum $$\sum_{i=1}^{n} d(i,p_i)$$ is maximal possible. If there are multiple optimal permutations, he wants to find the lexicographically smallest one. Help him with the task!
Input Format:
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.
Output Format:
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.
Note:
None