D. Treetime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard outputLittle 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  is maximal possible. If there are multiple optimal permutations, he wants to find the lexicographically smallest one. Help him with the task!InputThe 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.OutputIn the first line print the maximum possible value of the described sum. In the second line print n integers, representing the lexicographically smallest permutation.ExamplesInput21 2 3Output62 1Input51 2 21 3 32 4 42 5 5Output322 1 4 5 3
Input21 2 3
Output62 1
['graph matchings', '*3100']