MST - Minimum Spanning Tree


Find the minimum spanning tree of the graph.

Input

On the first line there will be two integers N - the number of nodes and M - the number of edges. (1 <= N <= 10000), (1 <= M <= 100000)
M lines follow with three integers i j k on each line representing an edge between node i and j with weight k. The IDs of the nodes are between 1 and n inclusive. The weight of each edge will be <= 1000000.

Output

Single number representing the total weight of the minimum spanning tree on this graph. There will be only one possible MST.

Example

Input:
4 5
1 2 10
2 3 15
1 3 5
4 2 2
4 3 40

Output:
17

hide comments
diegoenojado: 2017-04-18 06:40:57

Is it possible to achieve 100 points with Prim algorithm? Couldnt make it

sdfgsdgs: 2017-03-18 20:46:28

result 0 memory 0 time 0?

theo_pap1: 2017-03-04 16:23:12

I get 100 on result ... why isn't it accepted?
And time 0.01
MEM 23M

Last edit: 2017-03-04 16:24:05
Sajal Sarkar: 2017-01-02 11:55:48

Aren't partial problems counted in solved problems?

vanvinhbk94: 2016-12-01 14:58:35

AC in 1 go!!! easy Kruskal

rupeshyadav: 2016-11-08 02:51:08

i got 100 but not accepted what is this? can some one explain this to me?

bhedavivek: 2016-10-19 19:56:16

A little help pls, new to SPOJ
Getting this result, dont know what to do. Program words fine on given sample ouput as well as given sample input from my university
17972409 2016-10-19 19:54:43 krypton994 Minimum Spanning Tree 0 edit ideone it 0.00 0k PYTH 2.7

hung: 2016-10-13 08:28:52

Fucking Long long ==

avengers_2: 2016-08-29 22:47:48

why i am getting 36.36 only

sshuvo: 2016-08-11 20:52:51

"17486414 2016-08-11 20:48:49 sshuvo Minimum Spanning Tree 100 edit ideone it 0.08 "

is it an accepted code?i'm new in spoj


Added by:Nikola P Borisov
Date:2008-10-20
Time limit:1s-2s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ERL JS-RHINO NODEJS PERL6 VB.NET