← 返回题目列表

Codeforces · 468/D

D. 树

中文机器翻译题面 查看原题

小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