CF468D Tree

有一棵 $n$ 个节点的树（从 $1$ 到 $n$ 编号）。树上的每一个边权都是正值。定义两点 $u,v$ 之间的距离 $d(v,u)$ 为这两点最短路径边的权值之和。 设数列 $p$ 为一个 $1\sim n$ 的排列。求使得 $\sum\limits_{i=1}^n d(i,p_i)$ 最大的排列 $p$，若有多组解，求字典序最小的那个。

第一行是一个正整数 $n$（$1\le n\le10^5$）。 接下来 $n-1$ 行是三个整数 $u_i,v_i,w_i$（$1\le u_i,v_i\le n,1\le w_i\le10^5$），代表 $u_i$ 到 $v_i$ 有一条权值为 $w_i$ 的边。 数据保证这是一棵树。

第一行输出所求的最大和，第二行输出所求的排列。