There are n cities, m **bidirectional** roads connect to these n cities, each road has a cost. These m roads ensure that n cities connect to each other.

Please find out the minimum cost to connect these n cities.

Submit: 1200 Solved: 229

[Submit][Status][Web Board]

There are n cities, m **bidirectional** roads connect to these n cities, each road has a cost. These m roads ensure that n cities connect to each other.

Please find out the minimum cost to connect these n cities.

The first line contains two integers n, m \((1\leq n \leq 10^5, 1\leq m \leq 5*10^5)\), indicating there are n cities and m roads.

The next m lines, each line contains three integers u, v, w \((1\leq u, v \leq n, 1\leq w\leq 10^9)\), indicating that there is a road between u and v, cost w.

Please output the minimum cost to connect these n cities.

```
4 4
1 2 1
2 3 1
3 4 2
1 4 8
```

`4`