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
2016-01-05 20:41:20 Sukeesh
easy .. :)
2016-01-03 01:45:36
@sailemaverit partial score problems don't count
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.
2015-10-17 21:30:02 Osama Fathy
I am confused!
The same exact code gives 81.82% when I use "%I64d", but 100% when I use "%lld" !!
2015-08-09 14:26:11 (Tjandra Satria Gunawan)(曾毅昆)
@hoc sinh test: do the kid even care about spanning trees? :p
2015-07-23 15:41:32 hoc sinh test
Problem for kids :D

Last edit: 2015-07-23 17:17:08
2015-07-23 12:41:22 Ðức Tân
dễ vãi :D
2015-07-10 10:04:38 computer science
easy
2015-06-20 08:48:21 tarunsai
if we get 18.18 is it correct or not
2015-05-24 07:06:46 bholagabbar
Edit: Do not pick the first element from a vector and resize it again and again. This will case TLE as removing an element from the start of a vector causes it to resize taking O(n) time. Instead sort it in descending order nad keep poping the elements from the back which take O(1) time. I managed to get 100

Last edit: 2015-05-26 09:26:07
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.