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
abdelhameedddd: 2018-07-19 02:19:30

ac in one go

cnavneet: 2018-07-11 19:32:46

AC in one go.. Simple problem based on Kruskal's minimum spanning tree..

vd09: 2018-07-08 20:08:36

stuck in 91.92 point, what should i do now?

adityad1998: 2018-06-30 09:25:52

Simple Kruskal,exactly same as https://www.spoj.com/problems/CSTREET/.

coollllmann: 2018-05-04 15:08:21

int score: 81.82
long long int score: 100

ameyanator: 2018-04-25 08:31:01

81.82 points with int data type and 100 with long long int

ayushtewary07: 2018-02-17 16:21:33

Accepted in one go!
used prims algorithm

ramini1996: 2018-01-30 21:14:04

100 with Kruskal, AC in one go !!!

ramprosad: 2017-11-07 15:24:49

why isn't it accepted? I get 100 point.

Last edit: 2017-11-07 15:25:26
amit88265: 2017-08-23 19:02:33

i am using long long but still getting 18.18 and green!!!!!!....someone help please.


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