# Tree Diameter

AC一覧

## Problem Statement問題文

You are given a weighted undirected tree with $N$ vertices. The $i$-th edge bidirectionally connects vertices $a_i$ and $b_i$, and its weight is $c_i$.

Find a pair of vertices $(u, v)$ that are farthest apart, and output the path from $u$ to $v$.

$N$ 頂点の重み付き無向木が与えられる． $i$ 番目の辺は，頂点 $a_i$,$b_i$ 間に双方向に張られており，重みは $c_i$ である．

## Constraints制約

• All input are integers.
• $1 \leq N \leq 500{,}000$
• $0 \leq a_i, b_i \leq N - 1$
• $a_i \neq b_i$
• $1 \leq c_i \leq 10^{9}$
• 入力は全て整数である
• $1 \leq N \leq 500{,}000$
• $0 \leq a_i, b_i \leq N - 1$
• $a_i \neq b_i$
• $1 \leq c_i \leq 10^{9}$

## Input入力

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


## Output出力

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


$X$ is the sum of weights on the path, and $Y$ is the number of vertices on the path. $u_i$ and $u_{i+1}$ are the starting and ending vertices of the $i+1$-th edge traveled.

$X$ はパスの重みの総和，$Y$ はパスに含まれる頂点数を表す． $u_i$,$u_{i+1}$ はそれぞれ $i+1$ 番目に通る辺の始点と終点を表す．

## Sampleサンプル

### # 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


Timelimit: 5 secs

Before submitting, please confirm terms and conditions