Christmas Party

View as PDF

Points: 7 (partial)
Time limit: 2.0s
Java 3.5s
Python 3.5s
Memory limit: 128M
Java 256M
Python 256M

Author:
Problem type

Surge is hosting a Christmas party at his house and needs to stock up on juice!

Surge's town consists of houses and two-way roads connecting them. Surge lives in house . Each road takes minutes to walk across. He wants a person from every house in his neighbourhood to bring a bottle of juice to his house. What is the minimum total time that the citizens can spend walking from their house to Surge's house?

Constraints

In all test cases, for all

,

,

Input Specification

First line: (the number of houses) and (the number of roads).

The next lines each contain , , and indicating a two-way road connecting houses and and takes minutes to traverse ().

Output Specification

One integer: the minimum total time possible in minutes.

Sample Input 1

5 6
1 5 3
3 5 10
2 5 6
4 5 8
2 3 5
2 4 9

Output for Sample Case 1

36
Explanation for Sample Case 1

The town looks as such:

• House can go straight to house , taking minutes.
• House can go to house then house taking minutes.
• House can go to house then house taking minutes.
• House can go to house then house taking minutes.

The total time taken was minutes.