Problem Statement

Given a weighted undirected graph with n nodes and m edges, compute the total weight of the Minimum Spanning Tree (MST) using Kruskal's algorithm.

Algorithm:

1. Sort edges by weight (ascending).
2. Use Union-Find to greedily add edges: include an edge if it connects two different components.
3. Stop when n-1 edges have been added.
4. If fewer than n-1 edges can be added, the graph is disconnected — output "DISCONNECTED".

Function signature:

def mst_weight(n: int, edges: list) -> int | str:
    # edges: list of (u, v, weight)
    # returns total MST weight, or "DISCONNECTED" if no spanning tree exists

Input Format

Line 1: n m — number of nodes and edges
Lines 2..m+1: u v w — edge from u to v with weight w

Output Format

One line: the total MST weight (integer), or DISCONNECTED

Example

Input:

4 5
0 1 10
0 2 6
0 3 5
1 3 15
2 3 4

Output:

19

Notes

• Chosen edges: (2,3,4), (0,3,5), (0,2,6) — wait, that forms a cycle. Correct: (2,3,4), (0,3,5), (0,1,10) = 19.
• Use Union-Find with path compression and union by rank for efficiency.
• Nodes are 0-indexed.