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
Avneet: 2013-06-12 10:18:48

my solution got accepted , but result is 0 , wht it means ?

Lai Manh Tuan: 2013-01-10 10:55:14

@ Aman Gupta: Thanks for the suggestion

Aman Gupta: 2012-10-08 17:52:24

Anyone getting exactly 81.82 as their score should use long long. Both Prim's (with heap) and Kruskal's pass in time.

Last edit: 2012-10-09 11:20:42
Haidar Abboud: 2012-08-01 00:32:15

hope to see more textbook problems like this one -- useful to test the efficiency of your implementation

Giorgos Christoglou: 2012-02-24 15:19:49

@ Nicolas i quess WA ...

.::Manish Kumar::.: 2010-12-21 06:22:26

Last edit: 2012-03-30 11:48:26
যোবায়ের: 2010-06-16 18:44:48

A score of 100 means you have passed all the test data. In Partial problems, your score reflects the percentage of total correct answers your solution produced.

Nicholas James: 2009-03-19 19:58:34

I looked at the best solutions and don't understand how to scoring is done for this problem.


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