CF468D.Tree

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!

小 X 有一棵由 $n$ 个节点（编号为 $1$ 到 $n$）构成的树。树的每条边都有一个正长度。我们定义两个节点 $v$ 和 $u$ 之间的距离（记作 $d(v,\,u)$）为连接 $v$ 和 $u$ 的最短路径上所有边的长度之和。

一个排列 $p$ 是由 $n$ 个互不相同的整数 $p_1,\,p_2,\,...,\,p_n$ 构成的序列（其中 $1\le p_i\le n$）。小 X 希望找到一个排列 $p$，使得和式

取到最大可能值。如果存在多个最优排列，他希望从中找出字典序最小的一个。请帮助他完成这一任务！

The first line contains an integer n (1 ≤ n ≤ 105).

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 ≤  105), 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.

第一行包含一个整数 $n$（$1 \leq n \leq 10^5$）。

接下来的 $n-1$ 行中，每行包含三个以空格分隔的整数 $u_i$、$v_i$、$w_i$（$1 \leq u_i, v_i \leq n$；$1 \leq w_i \leq 10^5$），表示节点 $u_i$ 与 $v_i$ 之间存在一条长度为 $w_i$ 的边。

保证这些边构成一棵树。

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.

第一行输出所述和的最大可能值。
第二行输出 $n$ 个整数，表示字典序最小的排列。