Treasure Map Excavation

Little Ming has obtained an ancient treasure map during an archaeological dig. The map marks n hidden treasure houses buried deep underground and details m possible tunnels between them, each with a given length.

Excavating a tunnel from the surface to any treasure house is extremely difficult; however, the sponsor has agreed to clear a tunnel from the surface to one treasure house for free. Ming can choose which treasure house to connect to the surface.

Once a treasure house is connected (or excavated), Ming can then spend effort to excavate the passageways (roads) between treasure houses. Any road that has already been excavated can be traversed at no extra cost. When Ming excavates a new road, he and his team will dig out all treasures accessible through that road. Note that Ming does not wish to excavate "useless" roads, meaning if both treasure houses connected by a road have already been excavated, there is no need to excavate that road.

The cost to excavate a new road is given by \[ \mathrm{Cost} = L \times K, \] where L is the length of the road, and K is the number of treasure houses encountered on the unique path from the treasure house connected to the surface (by the sponsor) to the starting treasure house of the road (this count includes both endpoints). In other words, if the chosen road is excavated from a treasure house at a depth (number of houses from the sponsor, counting the sponsor house itself) of d, then the cost is \[ L \times (d+1). \]

Ming must choose the treasure house to be connected by the sponsor and then decide the order in which to excavate the roads such that all treasure houses become excavated and the total excavation cost is minimized. Compute and output this minimum total cost.

Note: The underlying process results in a tree (a spanning tree over the treasure houses) rooted at the sponsor‐connected treasure house. When a road is excavated from a treasure house at depth d, its excavation cost is \(L\times (d+1)\), and the newly excavated house will be at depth \(d+1\).

inputFormat

The first line contains two integers n and m — the number of treasure houses and the number of roads, respectively.

Each of the next m lines contains three integers u, v and w indicating that there is an undirected road between treasure houses u and v with length w (1-indexed).

outputFormat

Output a single integer — the minimum total cost required to excavate all treasure houses.

sample

3 3
1 2 3
2 3 4
1 3 5

16