Kruskal's Algorithm - Classic Problems | Repovive

CLS19. Kruskal's Algorithm

1s256 MB

Given an undirected weighted graph with $n$ vertices and $m$ edges, find the weight of the Minimum Spanning Tree (MST) using Kruskal's algorithm.

Kruskal's algorithm sorts edges by weight and greedily adds edges that don't form a cycle, using Union-Find (Disjoint Set Union).

If the graph is not connected, output -1.

\begin{array}{l} n \quad m \\ u_1 \quad v_1 \quad w_1 \\ u_2 \quad v_2 \quad w_2 \\ \vdots \\ u_m \quad v_m \quad w_m \end{array}

\begin{cases} \text{weight of MST} & \text{if the graph is connected} \\ -1 & \text{otherwise} \end{cases}

Input

Explanation

For this input, the required output is 7.

Output

Input

Explanation

For this input, the required output is 3.

Output

Input

4 2
1 2 5
3 4 3

Explanation

For this input, the required output is -1.

Output

-1

1s256 MB

Given an undirected weighted graph with $n$ vertices and $m$ edges, find the weight of the Minimum Spanning Tree (MST) using Kruskal's algorithm.

Kruskal's algorithm sorts edges by weight and greedily adds edges that don't form a cycle, using Union-Find (Disjoint Set Union).

If the graph is not connected, output -1.

\begin{array}{l} n \quad m \\ u_1 \quad v_1 \quad w_1 \\ u_2 \quad v_2 \quad w_2 \\ \vdots \\ u_m \quad v_m \quad w_m \end{array}

\begin{cases} \text{weight of MST} & \text{if the graph is connected} \\ -1 & \text{otherwise} \end{cases}

Input

Explanation

For this input, the required output is 7.

Output

Input

Explanation

For this input, the required output is 3.

Output

Input

4 2
1 2 5
3 4 3

Explanation

For this input, the required output is -1.

Output

-1