403171: GYM101059 F Minimize Tree

Given a weighted undirected tree of N nodes, rooted at the node 1. You can remove at most 1 edge and add another edge of same weight such that the resulting graph is still a tree. Minimize the sum of distances from node 1 to all other nodes.

The first line contains a single integer N, the size of the tree. Next N - 1 lines contain three space separated integers u, v and w, denoting an edge between the vertices u and v of weight w.

Constraints: 1 ≤ N ≤ 5 × 10⁴, 1 ≤ u, v ≤ N,  - 10³ ≤ w ≤ 10³

Output a single integer, the minimum sum of distances from node 1 to all other nodes.

2
1 2 3

3

4
1 2 61
1 3 -14
3 4 -47

-75