Prim's Algorithm - Classic Problems | Repovive

CLS20. Prim'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 Prim's algorithm.

Prim's algorithm starts from vertex 1 and greedily adds the minimum weight edge connecting the current tree to an unvisited vertex, using a priority queue.

If the graph is not connected, output -1.

Constraints

$1 \le n \le 10^5$
$0 \le m \le 2 \times 10^5$
$1 \le w_i \le 10^6$ (edge weights)

Input

\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}

Output

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

Samples

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

CLS20. Prim'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 Prim's algorithm.

Prim's algorithm starts from vertex 1 and greedily adds the minimum weight edge connecting the current tree to an unvisited vertex, using a priority queue.

If the graph is not connected, output -1.

Constraints

$1 \le n \le 10^5$
$0 \le m \le 2 \times 10^5$
$1 \le w_i \le 10^6$ (edge weights)

Input

\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}

Output

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

Samples

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