小X有一棵由n个节点组成的树(它们编号为1到n)。树的每条边都有正长度。让我们将两个节点 v 和 u 之间的距离(我们将其表示为 d(v, u))定义为 v 和 u 之间最短路径中的边长度之和。
排列 p 是 n 个不同整数 p1, p2, ..., pn (1 ≤ pi ≤ n) 的序列。小 X 想要找到一个排列 p,使得 $$\sum_{i=1}^{n} d(i,p_i)$$ 之和尽可能最大。如果有多个最优排列,他想找到字典顺序最小的一个。帮助他完成任务!
输入
第一行包含一个整数 n (1 ≤ n ≤ 105)。
接下来的 n - 1 行中的每一行都包含三个空格分隔的整数 ui, vi, wi (1 ≤ ui, vi ≤ n; 1 ≤ wi ≤ 105),表示节点 ui 和 vi 之间的一条边,长度等于 wi。
保证这些边形成一棵树。
输出
在第一行中打印所描述总和的最大可能值。在第二行中打印 n 个整数,表示按字典顺序排列的最小排列。
示例
输入 #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