Problem:
Minimum Spanning Tree Find the sum of weights of edges of the Minimum Spanning Tree for a given weighted undirected graph G = ( V , E ). Input  |V|  |E|  s 0  t 0  w 0  s 1  t 1  w 1 : s |E|-1  t |E|-1  w |E|-1  , where |V| is the number of vertices and |E| is the number of edges in the graph. The graph vertices are named with the numbers 0, 1,..., |V| -1 respectively.  s i and t i represent source and target verticess of i -th edge (undirected) and w i represents the weight of the i -th edge. Output Print the sum of the weights of the Minimum Spanning Tree. Constraints  1 ≤ |V| ≤ 10,000  0 ≤ |E| ≤ 100,000  0 ≤ w i ≤ 10,000  The graph is connected  There are no parallel edges  There are no self-loops  Sample Input 1 4 6
0 1 2
1 2 1
2 3 1
3 0 1
0 2 3
1 3 5 Sample Output 1 3 Sample Input 2 6 9
0 1 1
0 2 3
1 2 1
1 3 7
2 4 1
1 4 3
3 4 1
3 5 1
4 5 6 Sample Output 2 5

Solution (Python):
import sys
import queue
sys.setrecursionlimit(10 ** 6)


class UnionFind:
    def __init__(self, n):
        self.parents = [-1] * n  
        self.rank = [0] * n  

    def root(self, x):  
        if self.parents[x] == -1:  
            return x
        self.parents[x] = self.root(self.parents[x])
        return self.parents[x]

    def unite(self, x, y):
        x_root = self.root(x)
        y_root = self.root(y)

        if x_root == y_root:  
            return

        if self.rank[x_root] < self.rank[y_root]:
            self.parents[x_root] = y_root  
        elif self.rank[x_root] == self.rank[y_root]:
            self.parents[x_root] = y_root
            self.rank[y_root] += 1
        else:
            self.parents[y_root] = x_root
        return

    def is_in_same(self, x, y):  
        if self.root(x) == self.root(y):
            return True
        else:
            return False


def main():
    v, e = map(int, sys.stdin.readline().strip().split())

    edges = []
    for _ in range(e):
        s, t, w = map(int, sys.stdin.readline().strip().split())
        edges.append((s, t, w))

    edges = sorted(edges, key=lambda x: x[2])  

    ans = 0  

    unionfind = UnionFind(v)
    for s, t, w in edges:
        if unionfind.is_in_same(s, t):
            continue
        else:
            unionfind.unite(s, t)
            ans += w

    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
import sys
sys.setrecursionlimit(10**8)
def ii(): return int(sys.stdin.readline())
def mi(): return map(int, sys.stdin.readline().split())
def li(): return list(map(int, sys.stdin.readline().split()))
def li2(N): return [list(map(int, sys.stdin.readline().split())) for _ in range(N)]
def dp2(ini, i, j): return [[ini]*i for _ in range(j)]
def dp3(ini, i, j, k): return [[[ini]*i for _ in range(j)] for _ in range(k)]




class UnionFind:
    def __init__(self, n):
        self.d = [-1]*n
    
    def find(self, x):
        if self.d[x] < 0:
            return x
        else:
            self.d[x] = self.find(self.d[x])
            return self.find(self.d[x])
    
    def unite(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x==y:
            return False
        if self.d[x] > self.d[y]:
            x, y = y, x
        self.d[x] += self.d[y]
        self.d[y] = x
        return True
    
    def same(self, x, y):
        if self.find(x)==self.find(y):
            return True
        return False
    
    def size(self, x):
        return (-1) * self.d[self.find(x)]

V, E = mi()
stw = li2(E)
stw.sort(key=lambda x: x[2])

T = UnionFind(V)
cnt = 0

for i in range(E):
    s, t, w = stw[i][0], stw[i][1], stw[i][2]
    if not T.same(s, t):
        T.unite(s, t)
        cnt += w

print(cnt)

Solution (Python):

rank = []
p = []


def makeSet(x):
    p.append(x)
    rank.append(0)


def union(x, y):
    link(findSet(x), findSet(y))


def link(x, y):
    if rank[x] > rank[y]:
        p[y] = x
    else:
        p[x] = y
        if rank[x] == rank[y]:
            rank[y] = rank[y] + 1


def findSet(x):
    if x != p[x]:
        p[x] = findSet(p[x])
    return p[x]


def same(x, y):
    return findSet(x) == findSet(y)

def kruskal(g):
    MST = 0
    edges = g

    for e in edges:
        u = e[0]
        v = e[1]


        if findSet(u) != findSet(v):
            union(u, v)
            MST += e[2]

    return MST


V, E = map(int, input().split())
G = [list(map(int, input().split())) for i in range(E)]
G.sort(key=lambda x: x[2])

for i in range(V):
    makeSet(i)

print(kruskal(G))

Solution (Python):
from heapq import heappush, heappop, heapify
def prim(n, graph):
    used = [False] * n
    hq = [(w, v) for v, w in graph[0]]
    heapify(hq)
    used[0] = True
    res = 0
    while hq:
        w, v = heappop(hq)
        if used[v]:
            continue
        used[v] = True
        res += w
        for cv, cw in graph[v]:
            if used[cv]:
                continue
            heappush(hq, (cw, cv))
    return res

V, E = map(int, input().split())
graph = [[] for _ in range(V)]
for _ in range(E):
    s, t, w = map(int, input().split())
    graph[s].append((t, w))
    graph[t].append((s, w))
print(prim(V, graph))

Solution (Python):
class Kruskal_UnionFind():
    
    def __init__(self, N):
        self.edges = []
        self.rank = [0] * N
        self.par = [i for i in range(N)]
        self.counter = [1] * N

    def add(self, u, v, d):
        """
        u = from, v = to, d = cost
        """
        self.edges.append([u, v, d])

    def find(self, x):
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]

    def unite(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x != y:
            z = self.counter[x] + self.counter[y]
            self.counter[x], self.counter[y] = z, z
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
        else:
            self.par[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

    def size(self, x):
        x = self.find(x)
        return self.counter[x]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def Kruskal(self):
        """
        return: 最小全域木のコストの和
        """
        edges = sorted(self.edges, key=lambda x: x[2])  
        res = 0
        for e in edges:
            if not self.same(e[0], e[1]):
                self.unite(e[0], e[1])
                res += e[2]
        return res

v,e = map(int,input().split())
stw = [ list(map(int,input().split())) for _ in range(e) ]

T = Kruskal_UnionFind(v)
for i in range(e):
    s = stw[i][0] - 1
    t = stw[i][1] - 1
    w = stw[i][2]
    T.add(s,t,w)

print(T.Kruskal())

Solution (Python):
class UnionFind:
    def __init__(self, n):
        self.parent = [-1] * n

    def find(self, x):
        if self.parent[x] < 0:
            return x
        else:
            self.parent[x] = self.find(self.parent[x])
            return self.parent[x]

    
    def unite(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        
        if self.parent[x] > self.parent[y]:
            x, y = y, x
        self.parent[x] += self.parent[y]
        self.parent[y] = x

    
    def same(self, x, y):
        return self.find(x) == self.find(y)

    
    def size(self, x):
        return -self.parent[self.find(x)]


V, E = map(int, input().split())
edges = []
for _ in range(E):
    s, t, w = map(int, input().split())
    edges.append((w, s, t))
edges.sort()
uf = UnionFind(V)
ans = 0
for edge in edges:
    if uf.same(edge[1], edge[2]):
        continue
    ans += edge[0]
    uf.unite(edge[1], edge[2])
print(ans)

Solution (Python):
class UnionFind:
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def root(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.root(self.parents[x])
            return self.parents[x]

    def unite(self, x, y):
        x = self.root(x)
        y = self.root(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def same(self, x, y):
        return self.root(x) == self.root(y)


def main():

    V, E = map(int, input().split())

    
    edge_q = sorted([tuple(map(int, input().split())) for _ in range(E)], key=lambda x: x[2])

    
    ans = 0
    forest = UnionFind(V)
    for s, t, w in edge_q:
        if forest.same(s, t):
            continue
        forest.unite(s, t)
        ans += w
    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
import heapq
H = []
V, E = map(int, input().split())

for _ in range(E):
    s, t, w = map(int, input().split())
    
    heapq.heappush(H, (w, s, t))


class UnionFind:
    def __init__(self, n):
        self.parent = [-1] * n

    def root(self, a):
        if self.parent[a] < 0:
            return a
        else:
            self.parent[a] = self.root(self.parent[a])
            return self.parent[a]

    def size(self, a):
        return - self.parent[self.root(a)]

    def connect(self, a, b) -> bool:
        a = self.root(a)
        b = self.root(b)

        if a == b:
            return False

        if self.size(a) < self.size(b):
            a, b = b, a

        self.parent[a] += self.parent[b]
        self.parent[b] = a
        return True


unif = UnionFind(V)
ans = 0
while len(H) > 0:
    w, s, t = heapq.heappop(H)
    if unif.root(s) == unif.root(t):
        continue

    unif.connect(s, t)
    ans += w

print(ans)

Solution (Python):
import sys
input = sys.stdin.readline
from collections import deque
from heapq import heappush, heappop, heapify
    
def prim(V, E, v=0):
    
    
    visited = [False] * V
    visited[v] = True
    count = V-1
    
    dist = [float('inf')] * V
    dist[v] = 0
    
    q = list(E[v])
    heapify(q)
    
    for c, u in E[v]: dist[u] = c
    
    while count and q:
        c, v = heappop(q)

        if visited[v]: continue
    
        visited[v] = True
        count -= 1
        
        for c, u in E[v]:
            if visited[u]: continue
            dist[u] = min(dist[u], c)
            heappush(q, (dist[u], u))
    
    return dist

def main():
    V, e = map(int, input().split())
    E = [[] for i in range(V)]
    
    for i in range(e):
        v, u, c = map(int, input().split())
        E[v].append((c, u))
        E[u].append((c, v))

if __name__ == '__main__':
    V, e = map(int, input().split())
    
    E = deque(deque() for i in range(V))
    
    for i in range(e):
        v, u, c = map(int, input().split())
        
        E[v].append((c, u))
        E[u].append((c, v))
        
    print(sum(prim(V, E)))

Solution (Python):

import heapq

def main():
    n,m = map(int,input().split())
    e = [[] for _ in range(n)]
    for _ in range(m):
        a,b,c = map(int,input().split())
        e[a].append([b,c])
        e[b].append([a,c])

    inf = 1000000007
    d = [inf]*n
    d[0] = 0
    visited = [False]*n
    pq = [[0,0]]
    heapq.heapify(pq)
    while pq:
        c,v = heapq.heappop(pq)
        visited[v] = True
        for u,nc in e[v]:
            if not visited[u] and nc < d[u]:
                d[u] = nc
                heapq.heappush(pq,[nc,u])

    res = 0
    for i in range(n):
        res+=d[i]
    print(res)


if __name__ == '__main__':
    main()

Solution (Python):
class UnionFind:
    def __init__(self, N):
        
        
        self.vertices = [-1 for _ in range(N)]
        self.rank = [0] * N
        
    def find(self, v):
        if self.vertices[v] < 0: 
            return v
        else:
            
            self.vertices[v] = self.find(self.vertices[v])
            return self.vertices[v]
        
    def union(self, u, v):
        s1 = self.find(u) 
        s2 = self.find(v) 
        
        if s1 == s2: 
            return False
        
        if self.rank[s1] > self.rank[s2]: 
            self.vertices[s1] += self.vertices[s2] 
            self.vertices[s2] = s1
        else: 
            self.vertices[s2] += self.vertices[s1] 
            self.vertices[s1] = s2
            if self.rank[s1] == self.rank[s2]:
                self.rank[s2] += 1
        return True
        
    def is_connected(self, u, v):
        return self.find(u) == self.find(v)
    
    def size(self, v):
        return -self.vertices[self.find(v)]
        
    def is_connected(self, u, v):
        return self.find(u) == self.find(v)
    
    def size(self, v):
        return -self.vertices[self.find(v)]

class Kruskal:
    def __init__(self, N):
        self.N = N 
        self.E = []

    def add_edge(self, init, end, weight):
        self.E.append((weight, init, end))
        
    def min_spanning_tree(self):
        N, E = self.N, self.E
        weight = 0; edges = []
        n_edges = 0
        uf = UnionFind(N) 
        E = sorted(E)
        for w, a, b in E:
            if uf.union(a, b):
                edges.append((a, b))
                n_edges += 1; weight += w
            if n_edges == N - 1: break
        return edges, weight

N, M = map(int, input().split())
kr = Kruskal(N)
for _ in range(M):
    a, b, c = map(int, input().split())
    kr.add_edge(a, b, c)
_, ans = kr.min_spanning_tree()
print(ans)

Solution (Python):
v, e = map(int, input().split())
p = [i for i in range(v)]
E = [list(map(int, input().split())) for _ in range(e)]

E = sorted(E, key=lambda x: x[2])

def root(x):
  if p[x]==x:
    return x
  p[x] = root(p[x])
  return p[x]

ans = 0
for edg in E:
    a, b, w = edg
    if root(a)!=root(b):
        ans += w
        p[root(a)] = root(b)

print(ans)

Solution (Python):
V_0, E_0 = map(int, input().split())
from collections import deque
V = [False]*V_0
V[0] = True
E = 0
import heapq

S = []
heapq.heapify(S)
graph = [[] for i in range(V_0)]

for e in range(E_0):
    s, t, w = map(int, input().split())
    graph[s].append((w, t))
    graph[t].append((w, s))

for w, a in graph[0]:
    heapq.heappush(S, (w, a))

while len(S)!=0:
    w, a = heapq.heappop(S)
    if V[a]:
        continue
    for w2, b in graph[a]:
        if not V[b]:
            heapq.heappush(S, (w2, b))
    V[a] = True
    E += w

print(E)

Solution (Python):
import sys 
MOD = 10 ** 9 + 7
INF = 10**11
from heapq import heapify,heappush,heappop

def prim(n,G):
    ans = 0
    used = [0] * n
    used[0] = 1
    q = []
    for e,c in G[0]:
        heappush(q,(c,e))
    
    while len(q):
        c1,e1 = heappop(q)
        if used[e1]:
            continue
        used[e1] = 1
        for e2,c2 in G[e1]:
            if used[e2] == 0:
                heappush(q,(c2,e2))
        ans += c1
    return ans

def main():
    n,m = map(int,input().split())
    G = [[] for _ in range(n)]
    for _ in range(m):
        a,b,c = map(int,input().split())
        G[a].append((b,c))
        G[b].append((a,c))
    ans = prim(n,G)
    print(ans)
if __name__=='__main__':
    main()

Solution (Python):
class UnionFind():
    def __init__(self, n):
        self.n=n
        self.parents=[-1]*n 

    def find(self, x): 
        if self.parents[x]<0:
            return x
        else:
            self.parents[x]=self.find(self.parents[x])
            return self.parents[x]

    def union(self,x,y): 
        x=self.find(x)
        y=self.find(y)

        if x==y:
            return

        if self.parents[x]>self.parents[y]:
            x,y=y,x

        self.parents[x]+=self.parents[y]
        self.parents[y]=x

    def size(self,x): 
        return -self.parents[self.find(x)]

    def same(self,x,y): 
        return self.find(x)==self.find(y)

    def members(self,x): 
        root=self.find(x)
        return [i for i in range(self.n) if self.find(i)==root]

    def roots(self): 
        return [i for i, x in enumerate(self.parents) if x<0]

    def group_count(self): 
        return len(self.roots())

    def all_group_members(self): 
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())



import sys
input=sys.stdin.readline
v,e=map(int,input().split())
uf=UnionFind(v)
lis=[]
for i in range(e):
    x,y,w=map(int,input().split())
    lis.append([w,x,y])
import heapq
heapq.heapify(lis)

ans=0
for i in range(e):
    w,x,y=heapq.heappop(lis)
    if uf.same(x,y)==False:
        ans+=w
        uf.union(x,y)
    else:
        pass
print(ans)

Solution (Python):
import sys
input = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 7)


class UF_tree:
    def __init__(self, n):
        self.root = [-1] * (n + 1)  
        self.rank = [0] * (n + 1)

    def find(self, x):  
        if self.root[x] < 0:
            return x
        else:
            self.root[x] = self.find(self.root[x])
            return self.root[x]

    def isSame(self, x, y):
        return self.find(x) == self.find(y)

    def unite(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        elif self.rank[x] < self.rank[y]:
            self.root[y] += self.root[x]
            self.root[x] = y
        else:
            self.root[x] += self.root[y]
            self.root[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

    def getNodeLen(self, x):
        return -self.root[self.find(x)]


if __name__ == "__main__":
    N, M = map(int, input().split())
    edge = [tuple(map(int, input().split())) for _ in range(M)]
    edge.sort(key=lambda x: x[2])

    ans = 0
    uf = UF_tree(N)
    for s, t, c in edge:
        if uf.isSame(s, t):
            continue
        ans += c
        uf.unite(s, t)
    print(ans)

Solution (Python):
from heapq import *
def prim_heap():
    used = [False] * n
    e_lst = []
    for e in edge[0]:
        heappush(e_lst,e)
    used[0] = True
    res = 0
    while e_lst:
        e_min = heappop(e_lst)
        v = e_min[1]
        if used[v]: continue
        used[v] = True
        for e in edge[v]:
            if not used[e[1]]:
                heappush(e_lst, e)
        res += e_min[0]
    return res

n, k = map(int, input().split())
edge = [[] for _ in range(n)]
for _ in range(k):
    s, t, w = map(int, input().split())
    edge[s].append((w, t))
    edge[t].append((w, s))
print(prim_heap())

Solution (Python):

n, m = map(int, input().split())
stw = [list(map(int, input().split())) for _ in range(m)]
stw = sorted(stw, key=lambda x:x[2])

class UnionFind():
  def __init__(self, n):
    self.n = n
    self.root = [-1]*(n+1)
    self.rnk = [0]*(n+1)
  def Find_Root(self, x):
    if(self.root[x] < 0):
      return x
    else:
      self.root[x] = self.Find_Root(self.root[x])
      return self.root[x]
  def Unite(self, x, y):
    x = self.Find_Root(x)
    y = self.Find_Root(y)
    if(x == y):
      return 
    if self.root[x] > self.root[y]:
      x, y = y, x
    self.root[x] += self.root[y]
    self.root[y] = x 
  def isSameGroup(self, x, y):
    return self.Find_Root(x) == self.Find_Root(y)
  def Count(self, x): 
    return -self.root[self.Find_Root(x)]
  def Members(self, x): 
    return [i for i in range(self.n) if self.Find_Root(i)==self.Find_Root(x)]
  def Roots(self): 
    return [i for i, x in enumerate(self.root) if x < 0]
  def Group_Count(self): 
    return len(self.Roots())

def kruskal():
  res = 0 
  uf = UnionFind(n)
  for i in range(m):
    s, t, w = stw[i]
    if not uf.isSameGroup(s, t):
      uf.Unite(s, t)
      res += w 
  
  return res

print(kruskal())

Solution (Python):




class UnionFind():
    
    
    def __init__(self, n):
        self.n = n
        
        
        self.root = [-1]*(n+1)
        
        self.rnk = [0]*(n+1)

    
    def Find_Root(self, x):
        if(self.root[x] < 0):
            return x
        else:
            
            self.root[x] = self.Find_Root(self.root[x])
            return self.root[x]
    
    def Unite(self, x, y):
        
        x = self.Find_Root(x)
        y = self.Find_Root(y)
        
        if(x == y):
            return 
        
        elif(self.rnk[x] > self.rnk[y]):
            self.root[x] += self.root[y]
            self.root[y] = x

        else:
            self.root[y] += self.root[x]
            self.root[x] = y
            
            if(self.rnk[x] == self.rnk[y]):
                self.rnk[y] += 1
    
    def isSameGroup(self, x, y):
        return self.Find_Root(x) == self.Find_Root(y)

    
    def Count(self, x):
        return -self.root[self.Find_Root(x)]


V, E = map(int, input().split())
edges = []

for i in range(E):
    s, t, w = map(int, input().split())
    edges.append({"s": s, "t": t, "w": w})


edges = sorted(edges, key=lambda x:x['w'])
union_find = UnionFind(V)
res = 0
for i in range(E):
    edge = edges[i]
    if not union_find.isSameGroup(edge["s"], edge["t"]):
        union_find.Unite(edge["s"], edge["t"])
        res = res + edge["w"]
print(f"{res}")

Solution (Python):

from collections import defaultdict,deque
from heapq import heappush, heappop
from itertools import permutations
import sys
import math
import bisect
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    def root(x):
        if par[x] == x:
            return x
        par[x] = root(par[x])
        return par[x]

    def unite(x,y):
        x = root(x)
        y = root(y)
        if rank[x] < rank[y]:
            par[x] = y
        else:
            par[y] = x
            if rank[x] == rank[y]:
                rank[x] += 1

    n,m = LI()
    v = []
    for i in range(m):
        a,b,c = LI()
        v.append((c,a,b))
    v.sort()
    par = [i for i in range(n)]
    rank = [0]*n
    ans = 0
    for c,x,y in v:
        if root(x) != root(y):
            ans += c
            unite(x,y)
    print(ans)
    return


if __name__ == "__main__":
    solve()

Solution (Python):
import sys
import math
import string
import fractions
import random
from operator import itemgetter
import itertools
from collections import deque
import copy
import heapq
import bisect

MOD = 10 ** 9 + 7
INF = float('inf')
input = lambda: sys.stdin.readline().strip()


def minimum_spanning_tree(n, info):
    """
    頂点の数:nと辺の情報i:infoから最小全域木([[辺の始点の頂点,辺の終点の頂点, 重み], ...])を返す。
    info:[[辺の始点の頂点,辺の終点の頂点, 重み], ...](bellman_ford()の入力形式)
    """
    ans = []
    info.sort(key=itemgetter(2))

    class UnionFind:
        def __init__(self, n):
            self.n = n
            self.parents = [-1] * n

        def find(self, x):
            if self.parents[x] < 0:
                return x
            else:
                self.parents[x] = self.find(self.parents[x])
                return self.parents[x]

        def union(self, x, y):
            x = self.find(x)
            y = self.find(y)

            if x == y:
                return

            if self.parents[x] > self.parents[y]:
                x, y = y, x

            self.parents[x] += self.parents[y]
            self.parents[y] = x

        def size(self, x):
            return -self.parents[self.find(x)]

        def same(self, x, y):
            return self.find(x) == self.find(y)

        def members(self, x):
            root = self.find(x)
            return [i for i in range(self.n) if self.find(i) == root]

        def roots(self):
            return [i for i, x in enumerate(self.parents) if x < 0]

        def group_count(self):
            return len(self.roots())

        def all_group_members(self):
            return {r: self.members(r) for r in self.roots()}

        def __str__(self):
            return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

    uf = UnionFind(n)
    for i in info:
        if not uf.same(i[0], i[1]):
            ans.append(i)
            uf.union(i[0], i[1])
    return ans


V, E = map(int, input().split())
stw = [list(map(int, input().split())) for _ in range(E)]
print(sum([i[2] for i in minimum_spanning_tree(V, stw)]))

Solution (Python):
V, E = map(int, input().split())

PAR = list(range(V))
 
def root(x):
    if PAR[x] == x:
        return x
    else:
        PAR[x] = root(PAR[x])
        return PAR[x]
 
def same(x, y):
    return root(x) == root(y)
 
def unite(x, y):
    x = root(x)
    y = root(y)
    
    if x == y:
        return
    
    PAR[max(x, y)] = min(x, y)


class Edge:
    def __init__(self, u, v, cost):
        self.u = u
        self.v = v
        self.cost = cost
        
        

EDGES = []
for _ in range(E):
    s, t, w = map(int, input().split())
    EDGES.append(Edge(s, t, w))
    
def kruskal():
    edges = sorted(EDGES, key=lambda a: a.cost )
    res = 0
    for edge in edges:
        if (not same(edge.u, edge.v)):
            unite(edge.u, edge.v)
            res += edge.cost
    
    return res
    
print(kruskal())

Solution (Python):
import heapq

def prim():
    used = [1] * n
    used[0] = 0
    lis = []
    res = 0
    
    for q in edge[0]:
        heapq.heappush(lis,q)
        
    while lis:
        minedge = heapq.heappop(lis)
        
        if used[minedge[1]] == 0:
            continue

        v = minedge[1]
        used[v] = 0

        for q in edge[v]:
            if used[q[1]] == 1:
                heapq.heappush(lis , q )
        res += minedge[0]
    return res
    
n , m = map(int,input().split())
edge = [[] for _ in range(n)]

for _ in range(m):
    ad ,b ,c = map(int,input().split())
    edge[ad].append([c , b])
    edge[b].append([c , ad])
print(prim())

Solution (Python):
class UnionFind(object):
    def __init__(self, n):
        self.parent={i:i for i in range(1,n+1)}
        self.size={i:1 for i in range(1,n+1)}
    def find(self, a):
        if self.parent[a]!=a:
            self.parent[a]=self.find(self.parent[a])
        return self.parent[a]
    def getsize(self, a):
        return self.size[self.find(a)]
    def unite(self, a, b):
        a=self.find(a)
        b=self.find(b)
        if a==b:return
        if self.size[a]>self.size[b]:
            self.size[a]+=self.size[b]
            self.parent[b]=a
        else:
            self.size[b]+=self.size[a]
            self.parent[a]=b
    def isunited(self, a, b):
        return self.find(a)==self.find(b)


V, E = map(int, input().split())
uft = UnionFind(V)
l = [tuple(map(int, input().split())) for _ in range(E)]
l.sort(key=lambda x:x[2])

ans = 0
for s, t, w in l:
    s += 1; t += 1
    if not uft.isunited(s, t):
        ans += w
        uft.unite(s, t)

print(ans)

Solution (Python):
import heapq

num_V, num_E = map(int, input().split())
E = [[] for _ in range(num_V)]
for _ in range(num_E):
	ts,tt,tw = map(int, input().split())
	E[ts].append([tt,tw])
	E[tt].append([ts,tw])

flg = [0] * num_V
ans = []
q = []
heapq.heappush(q,[0,0])

while q:
	cd, cp = heapq.heappop(q)
	if flg[cp] == 0:
		flg[cp] = 1
		ans.append(cd)
	else:
		continue

	for np, nd in E[cp]:
		if flg[np] == 0:
			heapq.heappush(q,[nd, np])

print(sum(ans))

Solution (Python):
import math,itertools,bisect,sys,copy,queue

def LI(): return [int(x) for x in sys.stdin.readline().split()]

V,E = LI()
q = queue.PriorityQueue()
for _ in range(E):
    s,t,w = LI()
    q.put((w,s,t))

g = [i for i in range(V)]
root = [[i] for i in range(V)]

ans = 0
while not q.empty():
    w, s, t = q.get()
    if g[s] == g[t]: continue
    ans += w
    if len(root[g[s]]) < len(root[g[t]]):
        s ,t = t, s
    g_t = g[t]
    for i in root[g_t]:
        g[i] = g[s]
    root[g[s]].extend(root[g_t])
    root[g_t] = []

print (ans)

Solution (Python):
import sys
from heapq import heappush, heappop, heapify

V, E = map(int, sys.stdin.readline().strip().split())

graph = [[] for _ in range(V)]
for _ in range(E):
	s, t, w = map(int, sys.stdin.readline().strip().split())
	graph[s].append((w, t))
	graph[t].append((w, s))
	
used = set()
q = []
for i in range(V):
    if len(graph[i]):
        for w, t in graph[i]:
            q.append((w, t))
        used.add(i)
        break
heapify(q)

ans = 0
while q:
    w, s = heappop(q)
    if s in used:
        continue
    used.add(s)
    ans += w
    for w, t in graph[s]:
        if t in used:
            continue
        heappush(q, (w, t))

print(ans)

Solution (Python):
from heapq import heappush, heappop

INF = 10 ** 20

v_num, e_num= map(int, input().split())
edges_lst = [[] for _ in range(v_num)]
dist_lst = [INF for _ in range(v_num)]

min_dis = INF
for _ in range(e_num):
    s, t, dist = map(int, input().split())
    edges_lst[s].append((dist, t))
    edges_lst[t].append((dist, s))
    if min_dis > dist:
        min_dis = dist
        node1,node2 = s,t
    
if v_num==1:
    print(0)
else:
    que = []
    for v in edges_lst[node1]:
        heappush(que, v)
    for v in edges_lst[node2]:
        heappush(que, v)
        S = {node1,node2}
        ans = min_dis


    while len(S)!=v_num:
        dist, node = heappop(que)
        if node not in S:
            S.add(node)
            ans += dist
            for dist2 ,v in edges_lst[node]: 
                if v not in S:
                    heappush(que, (dist2, v))

    print(ans)

Solution (Python):
import heapq

V,E = map(int, input().split())

es = [[] for _ in range(V)]
q = []
for _ in range(E):
    s,t,w = map(int, input().split())
    heapq.heappush(q, (w,s,t))

class UnionFind:
    def __init__(self, N):
        self.parent = [i for i in range(N)]
        self.rank = [0] * N 
        self.count = 0 
    
    
    def root(self, a):
        if self.parent[a] == a:
            return a
        else:
            
            self.parent[a] = self.root(self.parent[a])
            return self.parent[a]
    
    
    def is_same(self, a, b):
        return self.root(a) == self.root(b)
    
    
    def unite(self, a, b):
        ra = self.root(a)
        rb = self.root(b)
        if ra == rb:
            return 
        if self.rank[ra] < self.rank[rb]:
            self.parent[ra] = rb
        else:
            self.parent[rb] = ra
            if self.rank[ra] == self.rank[rb]:
                self.rank[ra] += 1
        self.count += 1

uf = UnionFind(V)
total = 0
while q:
    w,s,t = heapq.heappop(q)
    if not uf.is_same(s,t):
        uf.unite(s,t)
        total += w

print(total)

Solution (Python):
from heapq import heappop,heappush,heapify

class Graph():
    def __init__(self,n,edge,directed=False):
        self.n = n
        self.graph = [[] for _ in range(n)]
        for e in edge:
            self.graph[e[0]].append((e[1],e[2]))
            if not directed:
                self.graph[e[1]].append((e[0],e[2]))
                
    def prim(self):
        used = [False for _ in range(self.n)]
        used[0] = True
        heap = [(cost,adj) for adj,cost in self.graph[0]]
        heapify(heap)
        res = 0
        while heap:
            cost,node = heappop(heap)
            if used[node]:
                continue
            used[node] = True
            res += cost
            for adj,adjcost in self.graph[node]:
                if used[adj]:
                    continue
                heappush(heap,(adjcost,adj))
        return res
        
import sys
input = sys.stdin.readline

V,E = map(int,input().split())
edge = [tuple(map(int,input().split())) for _ in range(E)]

g = Graph(V,edge)

print(g.prim())