34184번 - Opening Time

키보토스의 블랙마켓은 $N$개의 구역과, 구역 사이를 잇는 $N-1$개의 도로로 이루어져 있다. $i$번 도로는 구역 $A_i$와 $B_i$를 $W_i$의 길이로 잇는 도로이다. 또한, 임의의 두 구역 사이에는 항상 유일한 경로가 존재한다. 즉, 블랙마켓은 트리 구조를 이룬다.

$x$번 구역에는 상점 $x$가 위치해 있다. 내일, 상점은 처음으로 개점을 할 것이다. 첫 개점이기 때문에, 모든 $N$개의 구역으로부터 이 상점을 방문하기 위해 이동할 것이다. 하지만 사람이 한 곳에 너무 많이 몰리면 불만이 생길 수 있으므로, 한 구역에 가맹점을 하나 설치해, 각 구역에서는 본점과 가맹점 중 더 가까운 곳을 방문하게 하려고 한다. 모든 구역의 접근성을 고려하여, 다음 값을 최소화하려고 한다. 이 때, $y$는 가맹점의 위치이다.

$\displaystyle \max\limits_{1 \le i \le N}(\min(\textrm{distance}(x,\ i),\ \textrm{distance}(y,\ i)))$ (단, $\textrm{distance}(a,\ b)$는 구역 $a$와 구역 $b$ 사이의 거리)

$x = 1, 2,\cdots, N$ 에 대해, 적절히 가맹점을 잡았을 때 위 식의 최솟값을 구해주자.

첫 번째 줄에 양의 정수 $N$이 주어진다. $(2\le N\le 10^5)$

두 번째 줄부터 $N-1$개의 줄에 걸쳐 세 양의 정수 $A_i, B_i, W_i$가 공백을 사이에 두고 주어진다. $(1\le A_i, B_i\le N;\ A_i\neq B_i;\ 1\le W_i\le 10^9)$

$N$개의 정수를 공백을 사이에 두고 출력한다. $i$번째 정수는 $x=i$일 때의 위 식의 최솟값을 뜻한다.