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
mohibur_rahman: 2020-07-02 14:35:37

Can anybody tell me why my code shows result 100 instead of accept?

coolboy7: 2020-06-29 11:45:20


Last edit: 2020-07-01 07:56:21
zubrach08: 2020-04-16 17:05:21

i will do it with union find

nadstratosfer: 2020-03-20 22:51:17

Probably 6 correct answers out of 11 cases (6/11 = 0.54545).

master19: 2020-03-20 06:01:19

What does 54.55 indicate ??

codebreaker_00: 2020-03-05 12:07:11

O(logN)=0.57sec;
O(log(logN))=0.16sec;

codebreaker_00: 2020-03-05 09:40:30

Lite

coolio_1: 2020-02-25 17:43:09

100 means you passed 100% test cases. :)

hetp111: 2019-12-19 22:15:52

Time without path compression: 0.64 sec
Time with path compression: 0.07 sec

luka_: 2019-11-14 21:07:13

nice


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