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

vanvinhbk94: 2016-12-01 14:58:35

AC in 1 go!!! easy Kruskal

rupeshyadav: 2016-11-08 02:51:08

i got 100 but not accepted what is this? can some one explain this to me?

bhedavivek: 2016-10-19 19:56:16

A little help pls, new to SPOJ
Getting this result, dont know what to do. Program words fine on given sample ouput as well as given sample input from my university
17972409 2016-10-19 19:54:43 krypton994 Minimum Spanning Tree 0 edit ideone it 0.00 0k PYTH 2.7


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