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

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

정점이 $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$의 최솟값을 출력한다.