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
lokesh1997: 2017-08-02 15:11:02

what is this 18.18??

Last edit: 2017-08-02 15:50:58
jainaman1398: 2017-07-18 15:48:28

I did this using prims.AC in one go

trungpro: 2017-07-07 10:00:32

result is type long long in C++ or in64 in Pascal

Last edit: 2017-07-07 10:01:08
onkar14_n: 2017-06-26 15:41:34

AC in one go !!
Thanks to Kruskal Sir.

ravi_ndra12345: 2017-05-14 08:08:41

I am getting 81.82.
Does it mean 81.82 percent test cases passed?

sidku97: 2017-04-26 17:14:46

Getting 18.18 and green colour?
Does this mean it is ok?

diegoenojado: 2017-04-18 06:40:57

Is it possible to achieve 100 points with Prim algorithm? Couldnt make it

sdfgsdgs: 2017-03-18 20:46:28

result 0 memory 0 time 0?

theo_pap1: 2017-03-04 16:23:12

I get 100 on result ... why isn't it accepted?
And time 0.01
MEM 23M

Last edit: 2017-03-04 16:24:05
Sajal Sarkar: 2017-01-02 11:55:48

Aren't partial problems counted in solved problems?


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