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

mrinal_aich: 2016-07-20 17:12:02

Got 100% in one go...

roadblock: 2016-03-28 07:19:46

@harshgupta007: check for integer overflow

harshgupta007: 2016-03-10 06:32:32

I am getting 81.82. I am using JAVA. Any help would be very appreciated....
Oh got it. Just used long... Thanks all folks for the comments

Last edit: 2016-03-10 06:51:17
gohanssj9: 2016-02-03 16:40:52

Aman Gupta,
Thank you so much for the tip. I was getting 81.82.
Use long long to get 100

Last edit: 2016-02-03 16:41:19

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