training_2007_04_14 - SST for sparse graph

Problem G. SST for sparse graph ≡

problems
visible spaces
basic formulae
wide text
editor

Author:	StdAlg	Time limit:	1 sec
Input file:	input.txt	Memory limit:	8 Mb
Output file:	output.txt

Statement

You are to write a program that receives a weighted undirected graph and finds length of its shortest spanning tree.

Input file format

Input file contains two integers N, M. Vertices are numbered with integer numbers from 1 to N. M is the number of edges. Each of next M lines contain three integers describing an edge — numbers of vertices, connected by an edge and its weight respectively. All weights are positive. There is at most one edge connecting two vertices.

Output file format

Output file must contain a signle integer number — length of the SST. If it is impossible to construct spanning tree, output file must contain −1.

Constraints

1 ≤ N, M ≤ 100000 All weights are less or equal 1000.

Sample tests

No.	Input file (`input.txt`)	Output file (`output.txt`)
1	`3 3 1 2 10 2 3 10 3 1 10`	`20`