Competitions

# ADA Classes - November 6

# Minimal Spanning Tree

The connected graph is given. Find the spanning tree of minimal weight.

#### Input

The first line contains two integers **n** and **m** (**1** ≤ **n** ≤ **20000**, **0** ≤ **m** ≤ **100000**) - the number of vertices and number of edges in a graph. Each of the next **m** lines describes one edge. The edge number **i** is given with three integers `b`

, _{i}`e`

and _{i}`w`

(_{i}**1** ≤ `b`

, _{i}`e`

≤ _{i}**n**, **0** ≤ `w`

≤ _{i}**100000**) - the numbers of vertices and its weight.

Graph is connected.

#### Output

Print one number - the weight of the minimal spanning tree.

Input example #1

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

Output example #1

7