간선을 하나 그어서 루트까지 거리의 합을 최소로 만들기

트리는 사이클이 없는 단순 연결 그래프이다.

정점이 $N$개인 트리가 주어진다. 정점에는 1부터 $N$까지 번호가 매겨져 있다. 트리의 루트는 항상 정점 1이고, 간선은 양의 가중치를 갖는다.

이 트리에 다음 연산을 최대 한 번 사용할 수 있다.

• 임의의 정점 $u$와 $v$를 잇는 가중치가 $0$인 간선을 추가한다.

$d_i$를 정점 $i$에서 루트 정점까지의 최단 거리라고 하자. 연산을 한 번만 사용하여 $\sum_{i=1}^{N} d_i$를 최소화하는 프로그램을 작성하시오.

첫 번째 줄에 정점의 개수 $N$이 주어진다. $(1\leq N\leq 200\,000)$

두 번째 줄부터 $N-1$줄에 걸쳐 간선이 잇는 두 정점의 번호 $u$, $v$와 간선의 가중치 $w$가 공백으로 구분되어 주어진다. $(1\leq u,v\leq N;$ $1\leq w\leq 1\,000\,000)$

$\sum_{i=1}^{N} d_i$의 최솟값을 출력한다.