403171: GYM101059 F Minimize Tree
Memory Limit:256 MB
Time Limit:2 S
Judge Style:Text Compare
Creator:
Submit:0
Solved:0
Description
F. Minimize Treetime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output
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.
InputThe 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 × 104, 1 ≤ u, v ≤ N, - 103 ≤ w ≤ 103
OutputOutput a single integer, the minimum sum of distances from node 1 to all other nodes.
ExamplesInput2Output
1 2 3
3Input
4Output
1 2 61
1 3 -14
3 4 -47
-75