{"raw_statement":[{"iden":"statement","content":"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.\n\nThe 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.\n\n*Constraints:* 1 ≤ N ≤ 5 × 104, 1 ≤ u, v ≤ N,  - 103 ≤ w ≤ 103\n\nOutput a single integer, the minimum sum of distances from node 1 to all other nodes.\n\n"},{"iden":"input","content":"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 × 104, 1 ≤ u, v ≤ N,  - 103 ≤ w ≤ 103"},{"iden":"output","content":"Output a single integer, the minimum sum of distances from node 1 to all other nodes."},{"iden":"examples","content":"Input21 2 3Output3Input41 2 611 3 -143 4 -47Output-75"}],"translated_statement":null,"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ T = (V, E) $ be a weighted undirected tree with $ |V| = N $, rooted at node $ 1 $.  \nLet $ w(e) \\in \\mathbb{Z} $ denote the weight of edge $ e \\in E $, with $ |E| = N - 1 $.  \nLet $ d_T(u, v) $ denote the shortest path distance between nodes $ u $ and $ v $ in $ T $.  \nLet $ D_T = \\sum_{v \\in V \\setminus \\{1\\}} d_T(1, v) $ be the total distance from root $ 1 $ to all other nodes in $ T $.\n\n**Constraints**  \n1. $ 1 \\leq N \\leq 5 \\times 10^4 $  \n2. For each edge $ (u, v, w) \\in E $: $ 1 \\leq u, v \\leq N $, $ -10^3 \\leq w \\leq 10^3 $  \n3. Exactly one edge $ e \\in E $ may be removed, and one edge $ e' \\notin E $ of weight $ w(e) $ may be added, such that the resulting graph is still a tree.\n\n**Objective**  \nMinimize $ D_{T'} = \\sum_{v \\in V \\setminus \\{1\\}} d_{T'}(1, v) $ over all valid transformations $ T' $ of $ T $, where $ T' $ is obtained by replacing one edge $ e \\in E $ with another edge $ e' $ of the same weight such that $ T' $ remains a tree.","simple_statement":"You are given a tree with N nodes rooted at node 1. You can remove one edge and add one edge of the same weight to keep it a tree. Goal: minimize the total distance from node 1 to all other nodes.","has_page_source":false}