Problem Background

NOIP2017 Day 2 Task 2

Problem Description

Xiao Ming, who is participating in an archaeological excavation, has obtained a treasure map. The map marks $n$ hidden treasure rooms underground and also lists $m$ available roads between these rooms along with their lengths.

Xiao Ming is determined to excavate all the treasures in these rooms himself. However, each treasure room is very deep underground, meaning it is very difficult to dig a path from the surface to any treasure room. Digging paths between treasure rooms is relatively easier.

Xiao Ming's determination has moved the sponsor of the archaeological excavation, who has decided to sponsor him by digging a path from the surface to one of the treasure rooms for free. Xiao Ming gets to choose which room this path leads to.

On this basis, Xiao Ming also needs to consider how to dig paths between the treasure rooms. Once a path is dug, it can be traveled freely without any cost. Each time a new path is dug, Xiao Ming and the archaeological team will excavate the treasures that can be reached through that path. Additionally, Xiao Ming does not want to dig unnecessary paths; i.e., paths between already excavated treasure rooms do not need to be dug again.

The cost of digging a new path is $\mathrm{L} \times \mathrm{K}$, where $L$ represents the length of the path, and $K$ represents the number of treasure rooms (including the one sponsored by the sponsor and the starting room of the path) passed through from the sponsored room to the starting room of the path.

Please write a program to help Xiao Ming choose the treasure room for the sponsor to dig the path to and the subsequent paths to dig, such that the total cost is minimized, and output this minimum value.

Input Format

The first line contains two space-separated positive integers $n$ and $m$, representing the number of treasure rooms and the number of roads, respectively.

The next $m$ lines each contain three space-separated positive integers, representing the two treasure rooms connected by a road (numbered from $1$ to $n$) and the length $v$ of that road.

Output Format

A single positive integer representing the minimum total cost.

Sample Input and Output

Input Sample #1

4 5 
1 2 1 
1 3 3 
1 4 1 
2 3 4 
3 4 1 

Output Sample #1

4

Input Sample #2

4 5 
1 2 1 
1 3 3 
1 4 1 
2 3 4 
3 4 2  

Output Sample #2

5

Notes

Sample Explanation 1

Xiao Ming chose to have the sponsor dig to room 1. He developed the path 1 -> 2, excavating room 2. He developed the path 1 -> 4, excavating room 4. He also developed the path 4 -> 3, excavating room 3.

The total project cost is $1 \times 1 + 1 \times 1 + 1 \times 2 = 4$.

Sample Explanation 2

Xiao Ming chose to have the sponsor dig to room 1. He developed the path 1 -> 2, excavating room 2. He developed the path 1 -> 3, excavating room 3. He also developed the path 1 -> 4, excavating room 4.

The total project cost is $1 \times 1 + 3 \times 1 + 1 \times 1 = 5$.

Data Scale and Agreements

For 20% of the data: The input guarantees a tree structure, $1 \le n \le 8$, $v \le 5 \times 10^3$ and all $v$ are equal.

For 40% of the data: $1 \le n \le 8$, $0 \le m \le 10^3$, $v \le 5 \times 10^3$ and all $v$ are equal.

For 70% of the data: $1 \le n \le 8$, $0 \le m \le 10^3$, $v \le 5 \times 10^3$.

For 100% of the data: $1 \le n \le 12$, $0 \le m \le 10^3$, $v \le 5 \times 10^5$.

upd 2022.7.27: 50 additional Hack data sets have been added.

见题面 Input 部分

见题面 Output 部分