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
wxydth: 2022-08-25 14:48:51

You can use Boruvka's Algorithm

soumak: 2021-04-26 06:57:01

What is 9.09??

shubho5das: 2021-02-23 20:23:33

Try implementing both Kruskal's as well as Prim's

Last edit: 2021-03-09 13:22:19
ravi7526: 2021-02-11 12:21:23

what do mean by 9.09 error

kya_bantai: 2020-11-11 06:55:37

try to implement both prims's and krushal's algorithm

dodongchien123: 2020-09-12 15:59:28

This problem is another kind of judge. So 0 to 100 is your result, which 100 is fully passed (accepted).

abhishek__2007: 2020-07-25 12:26:58

my code is based on DISJOINT SET UNION taking O(1)*m time but why i am not getting 100pts.is am getting TLE on some TC;

i am using SPOJ first time if someone are free please help me.

[NG]: Don't post code here; use forum for questions.

Last edit: 2020-07-25 15:09:00
harsh_k: 2020-07-17 20:42:45

why is it showing 0 and not 100 as others have pointed. I think I solved it correctly as it shows green colour but still why 0

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

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