树的直径

【题目描述】

给定一棵有 $N$ 个顶点的带权无向树。

第 $i$ 条边双向连接顶点 $a_i$ 和 $b_i$，其权值为 $c_i$。

求一对距离最远的顶点 $(u, v)$，并输出从 $u$ 到 $v$ 的路径。

【输入】

$N$
$a_0$ $b_0$ $c_0$
$a_1$ $b_1$ $c_1$
$\vdots$
$a_{N-2}$ $b_{N-2}$ $c_{N-2}$

【输出】

$X$ $Y$
$u_0$ $u_1$ $\ldots$ $u_{Y-1}$

$X$ 是路径上的权值之和，$Y$ 是路径上的顶点个数。

$u_i$ 与 $u_{i+1}$ 分别是第 $i+1$ 条经过的边的起点与终点。

【输入样例】

8
0 1 5
1 2 3
2 3 1
1 4 2
4 7 4
1 5 7
2 6 5

【输出样例】

15 4
6 2 1 5

【数据范围】

• 所有输入均为整数。
• $1 \leq N \leq 500000$
• $0 \leq a_i, b_i \leq N - 1$
• $a_i \neq b_i$
• $1 \leq c_i \leq 1000000000$

【来源】

Library Checker（yosupo06） tree_diameter

本题为 special judge（输出任意合法解），暂不可本地评测。