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

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

hide comments
2015-04-18 13:55:54 Shounak Dey
Hey @Bharghav !!! How do we see your code?
2015-04-10 05:20:30 Mahesh Kohli
even after using long long , i am getting 81.82.Can somebody please help
2015-02-12 10:00:19 Bhargav Parsi
i am getting a compilation error although my code runs fine in ideone!..plz help
2015-01-11 09:44:31 Sonu Sharma
@paci :fair enough!!!
2014-11-09 10:51:39 Antony Skarlatos (Hepic)
Use long long for distance(or weight),to take 100%.
Also if you use printf dont use "%I64d",use "lld",because it happened to me. Good luck !!!
2014-09-26 20:51:21 Umair Khan
long long gives 100.
2014-06-14 10:29:43 ayush
Thank You Aman
2014-01-22 18:36:32 elgun
AC
[code removed]

See notes at bottom: "1. Don't post any source code here."

Last edit: 2014-01-22 22:05:08
2014-01-15 17:51:31 dslearner
isnt this problem same as http://www.spoj.com/problems/CSTREET/
but getting runtime in CSTREET while got this one accepted ....plz help

Last edit: 2014-01-15 17:56:55
2013-09-02 05:29:48 William Macfarlane
Aman Gupta,
Thank you so much for the tip. I was getting 81.82.
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.