Minimum Cost to Connect Streets

You are given a city represented as a graph with n intersections (vertices) and m possible routes (edges). Each route is described by three integers u, v, and w, where u and v are the intersections the route connects, and w is the cost to construct that route.

The goal is to compute the minimum total cost to connect all intersections. In other words, you need to form a spanning tree of the graph. Recall that a spanning tree for a graph with n vertices must have exactly n - 1 edges. If it is impossible to connect all intersections (i.e. the graph is disconnected), output -1.

You may use classical minimum spanning tree algorithms such as Kruskal's algorithm. In your solution, if a valid spanning tree cannot be formed, then return -1.

The relation for a spanning tree is given by $$|E| = n - 1$$ where \(n\) is the number of vertices and \(E\) is the set of edges in the spanning tree.

inputFormat

The input is read from stdin and has the following format:

1. The first line contains two integers, n (the number of intersections) and m (the number of routes).
2. Each of the following m lines contains three integers u, v, and w representing a route between intersections u and v with cost w.

outputFormat

Output a single integer to stdout indicating the minimum total cost to connect all intersections. If it's impossible to connect all intersections, output -1.

4 5
1 2 10
1 3 6
2 3 5
3 4 7
1 4 12

18