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 ![](https://cdn.luogu.com.cn/upload/vjudge_pic/CF468D/a49e43e6c1c8d0de94b03f979a5b3ad02f90fd6b.png) 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.

输入输出样例

输入样例 #1

2
1 2 3

输出样例 #1

6
2 1

输入样例 #2

5
1 2 2
1 3 3
2 4 4
2 5 5

输出样例 #2

32
2 1 4 5 3