Problem D: Kruskal’s Minimum Spanning Tree

CS F364 — Assignment 1

← Back to assignment

Problem

A spanning tree of an undirected graph is a subgraph that is a tree (connected and acyclic) and includes all vertices. A minimum spanning tree (MST) is a spanning tree whose total edge weight is minimised.

You are given an undirected weighted graph with \(n\) vertices and \(m\) edges. Find its MST. If the graph is disconnected, output DISCONNECTED. Otherwise output the total weight, the number of edges in the MST, and the edges themselves.

Input Format

• Line 1: n m — number of vertices \((1..n)\) and edges, with \(1 \le n \le 10^5\), \(1 \le m \le 2 \times 10^5\)
• Next \(m\) lines: u v w — an undirected edge between vertices \(u\) and \(v\) with integer weight \(w\) (\(-10^6 \le w \le 10^6\)). No self-loops.

Output Format

• Line 1: total weight of the MST (integer). If the graph is disconnected, output DISCONNECTED and stop.
• Line 2: integer \(k\) — number of edges in the MST
• Next \(k\) lines: u v w — edges in the MST, with \(u < v\), sorted lexicographically (by \(u\) then \(v\)).

Sample

Input

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

Output

6
3
1 2 1
2 3 2
2 4 3

Explanation: Edges in the MST: (1,2,1), (2,3,2), (2,4,3). Total weight 6.

Download sample input