Minimum Total Distance for City Network

You are given N cities and M roads. Each road connects two distinct cities and has an associated distance (or weight). Your task is to determine the minimum total distance required to connect all cities so that every city is reachable from every other city, i.e. find the weight sum of the Minimum Spanning Tree (MST) of the graph.

If it is impossible to connect all the cities (i.e. the graph is disconnected), output a single value 0 instead.

Note: The cities are numbered from 1 to N.

inputFormat

The first line contains two integers N and M separated by a space, where N is the number of cities and M is the number of roads.

The following M lines each contain three integers a, b and w separated by spaces, describing a road between cities a and b with distance w.

If M is 0, then no roads are given.

outputFormat

Output a single integer which is the minimum total distance required to connect all cities. If it is impossible to connect all the cities, output 0.

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

6