MST - Minimum Spanning Tree

Find the minimum spanning tree of the graph.


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.


Single number representing the total weight of the minimum spanning tree on this graph. There will be only one possible MST.


4 5
1 2 10
2 3 15
1 3 5
4 2 2
4 3 40


hide comments
hoc sinh test: 2015-07-23 15:41:32

Problem for kids :D

Last edit: 2015-07-23 17:17:08
Ðức Tân: 2015-07-23 12:41:22

dễ vãi :D

computer science: 2015-07-10 10:04:38


tarunsai: 2015-06-20 08:48:21

if we get 18.18 is it correct or not

bholagabbar: 2015-05-24 07:06:46

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
Shounak Dey: 2015-04-18 13:55:54

Hey @Bharghav !!! How do we see your code?

Mahesh Kohli: 2015-04-10 05:20:30

even after using long long , i am getting 81.82.Can somebody please help

Bhargav Parsi: 2015-02-12 10:00:19

i am getting a compilation error although my code runs fine in ideone!..plz help

Sonu Sharma: 2015-01-11 09:44:31

@paci :fair enough!!!

Antony Skarlatos (Hepic): 2014-11-09 10:51:39

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

Added by:Nikola P Borisov
Time limit:1s-2s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ERL JS-RHINO NODEJS PERL6 VB.NET