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
luka_: 2019-11-14 21:07:13

nice

sajalagrawal14: 2019-08-27 01:09:40

sol:-
1)prims:-https://ideone.com/ctzLgd
2)kurskals :-https://ide.codingblocks.com/s/122091

gourav_987: 2019-07-19 19:44:50

first time got ac in one go.100:))

mostafa_fares5: 2019-07-05 14:09:07

Last edit: 2019-07-05 14:32:11
bhavya_100000: 2019-07-02 06:20:24

Kruskals. AC in one go

coder_19: 2019-05-29 10:47:10

100 means what??
is that AC??

Last edit: 2019-05-29 10:47:38
zakir068: 2019-02-24 12:05:37

use long long

elmer_fudd: 2018-12-20 19:04:52

i get 100. is 100 means AC ?

az2019: 2018-12-05 07:13:22

54 is wrong about capacity

ameernsr: 2018-12-05 06:19:41

SALAM GUYS


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