It is guaranteed that any two cities reach each other using only roads.Bobo would like to build highways so that any two towns reach each using *only highways*.Building a highway between towns x and y costs him. δ(x,y) is the length of the shortest path between towns x and y using roads.As Bobo is rich, he would like to find the most expensive way to build the highways.
In ICPCCamp there were n towns conveniently numbered with 1, 2, dots, n 1,2,…,n connected with (n - 1) roads. The i-th road connecting towns a_i a i and b_i b i has length c_i c i . It is guaranteed that any two cities reach each other using only roads. Bobo would like to build (n - 1) highways so that any two towns reach each using *only highways*. Building a highway between towns x and y costs him delta(x, y) δ(x,y) cents, where delta(x, y) δ(x,y) is the length of the shortest path between towns x and y using roads. As Bobo is rich, he would like to find the most expensive way to build the (n - 1) highways.
（图片来源网络，侵删）
