Tree

### 题目大意 有一个n个节点的树（编号1~n）。树上的每一个边都是正值。 我们定义两点之间的距离$d(v,u)$为这两点最短路径边的权值之和。 设数列$p$为一个1~n的全排列。求使得$\sum_{i=1}^n d(i,p_i)$最大的、字典序列最小的全排列$p$。 ### 输入格式 第一行是一个正整数 $n (1 \le n \le 10^5) $ 接下来n-1行是三个整数$ u_{i},v_{i},w_{i} (1<=u_{i},v_{i}<=n; 1<=w_{i}<=10^{5}) $，分别代表$ u_{i}$到$v_{i}$有一条权值为$w_i$的路径 数据保证这是一棵树 ### 输出格式 第一行是所求的最大和 第二行是所求的字典序列最小的全排列

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<=10^{5}) $ . Each of the next $ n-1 $ lines contains three space separated integers $ u_{i},v_{i},w_{i} (1<=u_{i},v_{i}<=n; 1<=w_{i}<=10^{5}) $ , denoting an edge between nodes $ u_{i} $ and $ v_{i} $ with length equal to $ w_{i} $ . 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.

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