Mystery Crime Scenes: Minimum Spanning Tree

Holmes and Watson have encountered a series of mysterious crimes in London. Each crime scene is represented as a node and each clue linking two scenes is represented as an edge with a weight. Your task is to help them by finding the Minimum Spanning Tree (MST) that connects all the crime scenes with the minimum total clue weight. The MST weight is given by the sum of the weights of the selected edges:

$$ W = \sum_{edge \in MST} weight(edge) $$

If the graph is disconnected, assume the input is still valid and produce the MST for the connected components.

inputFormat

The first line contains two integers N and E, where N is the number of crime scenes (nodes) and E is the number of clues (edges). Each of the next E lines contains three integers u, v and w, indicating an undirected edge between nodes u and v with weight w.

outputFormat

Output a single integer, the total weight of the Minimum Spanning Tree (MST) that connects all the crime scenes.

4 5
1 2 5
1 3 10
2 3 4
2 4 11
3 4 8

17