Submit solution

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

##### Subtask 1 [50%]

,

##### Subtask 2 [50%]

,

#### 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.

## Comments