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
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
Sukeesh: 2016-01-05 20:41:20

easy .. :)

fallingstar: 2016-01-03 01:45:36

@sailemaverit partial score problems don't count

sailemaverit: 2015-11-05 07:04:10

I have solved this problem, getting a 100 in the result.
But this doesn't show in the count of my AC solutions.

Osama Fathy: 2015-10-17 21:30:02

I am confused!
The same exact code gives 81.82% when I use "%I64d", but 100% when I use "%lld" !!


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 NODEJS PERL 6 VB.net