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

sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
f_inf = float('inf')
mod = 10 ** 9 + 7


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):
        """
        yをxの根に繋ぐ
        """
        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 same(self, x, y):
        """
        xとyが同じ連結成分か判別する
        """
        return self.find(x) == self.find(y)

    def size(self, x):
        """
        xの連結成分の大きさを返す
        """
        return -self.parents[self.find(x)]

    def kruskal(self, edge):
        """
        :param edge: edge = [(コスト, 頂点1, 頂点2),...]の形で重み付き隣接リストを渡して下さい
        :return: 最小全域木のコストの和
        """
        edge.sort()
        cost_sum = 0
        for cost, node1, node2 in edge:
            if not self.same(node1, node2):
                cost_sum += cost
                self.union(node1, node2)
        return cost_sum


def resolve():
    V, E = map(int, input().split())
    edge = []
    for _ in range(E):
        s, t, w = map(int, input().split())
        edge.append([w, s, t])

    uf = UnionFind(V)
    res = uf.kruskal(edge)
    print(res)


if __name__ == '__main__':
    resolve()

Solution (Python):
V, E = map(int, input().split())
inf = float('inf')
graphs = [list(map(int, input().split())) for _ in range(E)]

graphs.sort(key=lambda x: x[2])


nodes = [i for i in range(V)]
cost = 0


def root(node):
    if nodes[node] == node:
        return node
    nodes[node] = root(nodes[node])
    return nodes[node]


for i, j, k in graphs:
    if not root(i) == root(j):
        cost += k
        nodes[root(i)] = root(j)
print(cost)

Solution (Python):
v, e = map(int, input().split())

from heapq import heappush, heappop
edges = []
for _ in range(e):
    s, t, w = map(int, input().split())
    heappush(edges, (w, s, t))


par = [-1] * v
rank = [0] * v

def find(x):
    """ 根ノードの値を見つけて返す """
    if par[x] < 0:
        return x
    else:
        par[x] = find(par[x])
        return par[x]

def unite(x, y):
    """xとyを結合する"""
    rootx = find(x)
    rooty = find(y)

    if rootx == rooty:
        return False
    else:
        if rank[rootx] < rank[rooty]:
            par[rootx] = rooty
        else:
            par[rooty] = rootx
            if rank[rootx] == rank[rooty]: rank[rootx] += 1
        return True

def same(x, y):
    """ xとyが同じ集合に属しているか """
    return find(x) == find(y)

ans = 0
while edges:
    w, s, t = heappop(edges)
    if not same(s, t):
        ans += w
        unite(s, t)

print(ans)

Solution (Python):
class UnionFind:
    def __init__(self, n):
        self.n = n
        self.par = [i for i in range(n)]
        self.rank = [0 for i in range(n)]
        self.siz = [1 for i in range(n)]
    
    def find(self, x):
        if self.par[x] == x:
            return x
        return self.find(self.par[x])
    
    def unite(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if self.rank[x] > self.rank[y]:
            self.par[y] = x
            self.siz[x] += self.siz[y]
        else:
            self.par[x] = y
            self.siz[y] += self.siz[x]
            if self.rank[x] == self.rank[y]:
                self.rank[y] += 1
    
    def same(self, x, y):
        return self.find(x) == self.find(y)
    
    def size(self, x):
        return self.siz[self.find(x)]
    
def kruskal(n, m):
    res = 0
    uf = UnionFind(n)
    for i in range(m):
        w, s, t = es[i]
        if uf.same(s, t):
            continue
        uf.unite(s, t)
        res += w
    return res

V, E = map(int, input().split())
es = []
for i in range(E):
    s, t, w = map(int, input().split())
    es.append([w, s, t])

es.sort(key=lambda x: x[0])
res = kruskal(V, E)
print(res)

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

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

  def union(self, u, v):
    p1, p2 = self.find(u), self.find(v)
    if p1 == p2: return

    if self.parents[p1] > self.parents[p2]:
      p1,p2 = p2,p1

    self.parents[p1] += self.parents[p2]
    self.parents[p2] = p1

  def same(self, u, v):
    return self.find(u) == self.find(v)

V,E = map(int,input().split())
edges = []
for i in range(E):
  s,t,w = map(int,input().split())
  edges.append((w,s,t))
edges.sort(key=lambda x: x[0])

uf = UF(V)
ans = 0
for i in range(E):
  w,s,t = edges[i]
  if not uf.same(s,t):
    uf.union(s,t)
    ans += w

print(ans)

Solution (Python):
class UnionFind:
    def __init__(self, n):
        self.p = [i for i in range(n)]
        self.rank = [1]*n
    
    def root(self, x):
        if x == self.p[x]:
            return x
        self.p[x] = y = self.root(self.p[x])
        return y
    
    def unite(self, x, y):
        px = self.root(x); py = self.root(y)
        if px == py:
            return 0
        rx = self.rank[px]; ry = self.rank[py]
        if ry < rx:
            self.p[py] = px
        elif rx < ry:
            self.p[px] = py
        else:
            self.p[py] = px
            self.rank[px] += 1
        return 1

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

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

union_find = UnionFind(V+1)
ans = 0
for s,t,w in STW:
    if not union_find.same(s,t):
        ans += w
        union_find.unite(s,t)

print(ans)

Solution (Python):
class UnionFind():
    def __init__(self,n):
        self.n=n
        self.parents = [i for i in range(n+1)]
        self.size = [1]*(n+1)
    def find(self,x):
        if self.parents[x]==x:
            return x
        else:
            self.parents[x]=self.find(self.parents[x])
            return self.parents[x]
    def unite(self,x,y):
        xRoot = self.find(x)
        yRoot = self.find(y)
        if xRoot == yRoot:
            return
        if self.size[xRoot]>self.size[yRoot]:
            self.parents[yRoot] = xRoot
            self.size[xRoot] += self.size[yRoot]
            self.size[yRoot] = 0
        else:
            self.parents[xRoot] = yRoot
            self.size[yRoot] += self.size[xRoot]
            self.size[xRoot] = 0

V,E = map(int,input().split())
tree = UnionFind(V)
edges = [list(map(int,input().split())) for _ in range(E)]
edges.sort(key=lambda x: x[2])
cost = 0
for s,t,w in edges:
    if tree.find(s) != tree.find(t):
        cost += w
        tree.unite(s,t)

print(cost)

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

    def find(self, x):
        '''
        要素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が属するグループと要素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):
        '''
        要素xが属するグループのサイズ（要素数）を返す
        '''
        return -self.parents[self.find(x)]

    def same(self, x, y):
        '''
        要素x, yが同じグループに属するかどうかを返す
        '''
        return self.find(x) == self.find(y)

    def members(self, x):
        '''
        要素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())

def kruskal(v: int, edges: list):
    """
    v: 頂点数
    edges: 各辺のstart end weightのリスト
    """
    edges.sort(key=lambda edge: edge.weight)
    uf = UnionFind(v)
    mst = []
    for edge in edges:
        if not uf.same(edge.start, edge.end):
            uf.union(edge.start, edge.end)
            mst.append(edge)
    return mst

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

from collections import namedtuple
Edge = namedtuple("Edge", ['start', 'end', 'weight'])
edges = []
for _ in range(E):
    s, t, w = map(int, input().split())
    edges.append(Edge(s, t, w))

mst = kruskal(V, edges)
print(sum([e.weight for e in mst]))

Solution (Python):
import sys
import itertools

import time
import math
 
sys.setrecursionlimit(10 ** 7)
 
from collections import defaultdict
 
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines




class UnionFind(object):
    def __init__(self, n = 1):
        self.link = [i for i in range(n)]
        self.size = [1 for _ in range(n)]

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

        
        
        self.link[x] = self.find(self.link[x])
        return self.link[x]

    def is_same(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

        if self.size[x] < self.size[y]:
            x, y = y, x
        self.link[y] = x
        self.size[x] += self.size[y]
    
    def get_size(self, x):
        x = self.find(x)
        return self.size[x]


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

edges = [0] * E
for i in range(E):
    s, t, w = map(int, input().split())
    edges[i] = (w, s, t)

u = UnionFind(V)

edges = sorted(edges)

ans = 0
for e in edges:
    w, s, t = e
    if u.is_same(s, t):
        continue
    u.unite(s, t)
    ans += w
print(ans)

Solution (Python):
v,e=map(int,input().split())
s=sorted([list(map(int,input().split()))for i in range(e)],key=lambda x:x[2])
d=[i for i in range(v)]
def f(x):
    if x==d[x]:
        return x
    d[x]=f(d[x])
    return f(d[x])
a=0
for i,j,h in s:
    i,j=f(i),f(j)
    if i!=j:
        d[i]=j
        a+=h
print(a)

Solution (Python):
import sys
sys.setrecursionlimit(10000)

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

def unite(x, y):
    rx = root(x)
    ry = root(y)
    if rx != ry:
        par[rx] = ry

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

n, m = map(int, input().split())
E = []
for i in range(m):
    s, t, w = map(int, input().split())
    E.append([w, s, t])

E.sort()

par = [i for i in range(n)]

ans = 0

for e in E:
    if not same(e[1], e[2]):
        unite(e[1], e[2])
        ans += e[0]

print(ans)

Solution (Python):
class UnionFind:
    def __init__(self, n):
        self.n = n
        self.parent = [i for i in range(n)]  
        self.rank = [1] * n  
        self.size = [1] * n  
 
    def find(self, x):  
        if self.parent[x] == x:
            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:
            if self.rank[x] < self.rank[y]:
                self.parent[x] = y
                self.size[y] += self.size[x]
            else:
                self.parent[y] = x
                self.size[x] += self.size[y]
                if self.rank[x] == self.rank[y]:
                    self.rank[x] += 1
 
    def is_same(self, x, y):  
        return self.find(x) == self.find(y)
 
    def group_size(self, x):  
        return self.size[self.find(x)]

def kruskal(max_vertex,edges):
    edges.sort(key=lambda x:x[2])
    uf=UnionFind(max_vertex)
    mst=[]
    for edge_cost in edges:
        es,ee,cost=edge_cost
        if not uf.is_same(es,ee):
            uf.unite(es,ee)
            mst.append([(es,ee),cost])
    return mst
         



v,e=map(int,input().split())
graph=[]
for i in range(e):
    f,s,cost=map(int,input().split())
    graph.append([f,s,cost])

ans=0
for i in kruskal(v,graph):
    ans+=i[1]
print(ans)

Solution (Python):
from operator import itemgetter

class UnionFindTree:
    def __init__(self,size):
        self.rank=[0]*size
        self.p=[0]*size
        for i in range(size):
            self.makeSet(i)
    
    def makeSet(self,i):
        self.p[i]=i
        self.rank[i]=0
    
    def same(self,x,y):
        return self.findSet(x) == self.findSet(y)
    
    def unite(self, x,y):
        self.link(self.findSet(x), self.findSet(y))
    
    def link(self, x, y):
        if(self.rank[x] > self.rank[y]):
            self.p[y] = x
        else:
            self.p[x] = y
            if self.rank[x] == self.rank[y]:
                self.rank[y]+=1
     
    def findSet(self, x):
        if(x!=self.p[x]):
            self.p[x]=self.findSet(self.p[x])
        return self.p[x]

    def print(self):
        print(self.p)


def readinput():
    nv, ne=list(map(int,input().split()))
    nList=[]
    for _ in range(ne):
        s,t,w=list(map(int,input().split()))
        nList.append((s,t,w))
    return nv,ne,nList

def Kruskal(nv,nList):
    sortedList=sorted(nList, key=itemgetter(2))
    S=UnionFindTree(nv)
    K=[]

    for e in sortedList:
        s=e[0]
        t=e[1]
        if S.same(s,t)==False:
            S.unite(s,t)
            K.append(e)
    
    return K

def main(nv,ne,nList):
    K=Kruskal(nv,nList)
    total=0
    for e in K:
        total+=e[2]
    return total


if __name__=='__main__':
    nv,ne,nList=readinput()
    ans=main(nv,ne,nList)
    print(ans)

Solution (Python):


import sys
iim = lambda: map(int, sys.stdin.readline().rstrip().split())

def resolve():
    it = map(int, sys.stdin.read().split())
    V, E = next(it), next(it)

    ee = [-1] * V
    def find(a):
        q = []
        while ee[a] >= 0:
            q.append(a)
            a = ee[a]
        for i in q:
            ee[i] = a
        return a
    def union(a, b):
        ai = find(a)
        bi = find(b)

        r1, r2 = ee[ai],  ee[bi]
        if r1 > r2:
            ai, bi = bi, ai

        ee[bi] = ai
        if r1 == r2:
            ee[ai] -= 1
    def same(a, b):
        ai = find(a)
        bi = find(b)

        return ai == bi

    ans = 0
    for si, ti, wi in sorted(zip(it, it, it), key=lambda x: x[2]):
        if same(si, ti):
            continue
        ans += wi
        union(si, ti)

    print(ans)

if __name__ == "__main__":
    resolve()

Solution (Python):
class Edge():
    def __init__(self, src, to, weight):
        self.src = src
        self.to = to
        self.weight = weight

    def __lt__(self, other):
        return self.weight < other.weight

class Edges():
    def __init__(self):
        self.E = []
    
    def append(self, src, to, weight=0):
        self.E.append(Edge(src, to, weight))

    def getInOrderByASC(self):
        return sorted(self.E)

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 unite(self, x, y):
        x, y = self.find(x), 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 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 __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())


class MinimumSpanningTree():
    def __init__(self, V, edges):
        self.V = V
        self.E = edges

    
    def kruskal(self):
        U = UnionFind(self.V)
        total = 0
        for e in self.E.getInOrderByASC():
            if not U.same(e.src, e.to):
                total += e.weight
                U.unite(e.src, e.to)
        return total


V,E = map(int, raw_input().split())
edges = Edges()
for i in range(E):
    s,t,w = map(int, raw_input().split())
    edges.append(s,t,w)

mst = MinimumSpanningTree(V, edges)
print mst.kruskal()

Solution (Python):
from sys import setrecursionlimit

class UnionFind:
    def __init__(self, n):
        
        
        self.par = [i for i in range(n + 1)]
        
        self.rank = [0] * (n + 1)
        self.size = [1] * (n + 1)

    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 check(self, x, y):
        
        return self.find(x) == self.find(y)


    def union(self, x, y):
        
        x = self.find(x)
        y = self.find(y)
        if x == y:return
        
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
            self.size[y] += self.size[x]
        else:
            self.par[y] = x
            self.size[x] += self.size[y]
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

    def count_group(self, n):
        return len({self.find(x) for x in range(1, n + 1)})

v ,e = map(int, input().split())
stw = [list(map(int, input().split())) for i in range(e)]
stw.sort(key=lambda x:x[-1])
uf = UnionFind(v)

rec = 0
for s, t, w in stw:
    if not uf.check(s, t):
        uf.union(s, t)
        rec += w
print(rec)

Solution (Python):

def find(x):
    global uf
    if uf[x]<0:
        return x
    else:
        uf[x] = find(uf[x])
        return uf[x]
    
def union(x, y):
    """
    Input: x, y
          x,y are vertex in tree.
    Return: bool
          False: not union. x,y are in same tree.
          True: do union. x,y are not in same tree.
    """
    global uf
    x, y = find(x), find(y)
    if x==y:
        return False
    else:
        if uf[x]<uf[y]:
            x, y = y, x
        uf[x] += uf[y]
        uf[y] = x
        return True
    
V, E = map(int, input().split())
edges = []
for _ in range(E):
    edges.append(tuple(map(int, input().split())))
    
uf = [-1]*V



mst = []
for e in sorted(edges, key=lambda x: x[2]):
    if find(e[0])!=find(e[1]):
        union(e[0], e[1])
        mst.append(e)
print(sum(map(lambda x: x[2], mst)))

Solution (Python):
v,e=map(int,input().split())
if e==0:print(0);exit()
class UnionFind:
    
    
    __slots__ = ["_size", "_first_idx", "_parents"]
    def __init__(self, size: int, first_index: int = 0) -> None:
        self._size = size
        self._first_idx = first_index
        self._parents = [-1] * (size + first_index)
    def find(self, x: int) -> int:
        if self._parents[x] < 0:
            return x
        self._parents[x] = self.find(self._parents[x])
        return self._parents[x]
    def same(self, x: int, y: int) -> bool:
        return self.find(x) == self.find(y)
    def unite(self, x: int, y: int) -> bool:
        x, y = self.find(x), self.find(y)
        if x == y:
            return False
        if self._parents[x] > self._parents[y]:
            x, y = y, x
        self._parents[x] += self._parents[y]
        self._parents[y] = x
        return True
    def size(self, x: int) -> int:
        return -self._parents[self.find(x)]
    def group_count(self) ->int:
        return sum(1 for i in  self._parents if i<0)-self._first_idx
    def connected(self) ->bool:
        return self._parents[self.find(self._first_idx)]==-self._size
edges=sorted([list(map(int,input().split())) for i in range(e)],key=lambda x:x[-1])
uf=UnionFind(v)
n,m,su=edges[0]
uf.unite(n,m)
for a,s,d in edges:
    if uf.same(a,s):continue
    uf.unite(a,s);su+=d
    if uf.size(n)==v:print(su);exit()

Solution (Python):
import heapq

def prim_heap():
    used = [True] * n 
    edgelist = []
    for e in edge[0]:
      heapq.heappush(edgelist,e)
    used[0] = False
    res = 0
    while len(edgelist) != 0:
        minedge = heapq.heappop(edgelist)
        if not used[minedge[1]]:
            continue
        v = minedge[1]
        used[v] = False
        for e in edge[v]:
            if used[e[1]]:
                heapq.heappush(edgelist,e)
        res += minedge[0]
    return res


n,w = map(int,input().split())

edge = [[] for i in range(n)]

for i in range(w):
    x,y,z = map(int,input().split())
    
    edge[x].append([z,y])
    edge[y].append([z,x])
print(prim_heap())

Solution (Python):
import heapq


class UnionFind:
    from collections import deque

    def __init__(self, v):
        self.v = v
        self._tree = list(range(v + 1))

    def _root(self, a):
        queue = self.deque()
        while self._tree[a] != a:
            queue.append(a)
            a = self._tree[a]
        while queue:
            index = queue.popleft()
            self._tree[index] = a
        return a

    def union(self, a, b):
        root_a = self._root(a)
        root_b = self._root(b)
        self._tree[root_b] = root_a

    def find(self, a, b):
        return self._root(a) == self._root(b)


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

uf = UnionFind(V)
cost = 0
while heap:
    w, s, t = heapq.heappop(heap)
    if not uf.find(s, t):
        uf.union(s, t)
        cost += w

print(cost)

Solution (Python):
num_V, num_E = map(int, input().split())

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())

root = []
for i in range(num_E):
    s, t, w = map(int, input().split())
    root.append((s,t,w))

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

uf = UnionFind(num_V)
ans = 0

for s, t, w in root:
    if uf.same(s,t):
        continue
    else:
        uf.union(s,t)
        ans += w

print(ans)

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


class PriorityQueue:
    def __init__(self):
        self._queue = []

    def push(self, value):
        heappush(self._queue, value)

    def pop(self):
        return heappop(self._queue)

    @property
    def empty(self):
        return not self._queue

    def __len__(self):
        return len(self._queue)

    def __contains__(self, item):
        return item in self._queue


v, e = map(int, input().split())
if v == 1:
    print(0)
    sys.exit()
edge = [[] for _ in range(v)]
for _ in range(e):
    s, t, w = map(int, input().split())
    
    edge[s].append((w, t))
    edge[t].append((w, s))

V = set()
pq = PriorityQueue()
weight = 0
V.add(0)
for i in edge[0]:
    pq.push(i)

while True:
    nw, nv = pq.pop()
    if nv in V:
        continue
    else:
        weight += nw
        V.add(nv)
        for i in edge[nv]:
            pq.push(i)

    if len(V) == v:
        break

print(weight)

Solution (Python):
class Edge:
    def __init__(self, u, v, cost):
        self.u = u
        self.v = v
        self.cost = cost
    
    def __str__(self):
        return "u: " + str(self.u) + " v: " + str(self.v) + " cost: " + str(self.cost)

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 unite(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 isSame(self, x, y):
        return self.find(x) == self.find(y)

def solve():
    V, E = map(int,input().split())
    edges = []
    for i in range(E):
        s,t,w = map(int,input().split())
        e = Edge(s,t,w)
        edges.append(e)
    
    edges.sort(key=lambda e: e.cost)

    uf = UnionFind(V+1)

    ans = 0
    for edge in edges:
        if not uf.isSame(edge.u, edge.v):
            uf.unite(edge.u, edge.v)
            ans += edge.cost

    print(ans)

if __name__ == '__main__':
    solve()

Solution (Python):
import sys

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())

def main():
    V, E = map(int, input().split())
    uf = UnionFind(V)
    edges = []
    for _ in range(E):
        s, t, w = map(int, input().split())
        edges.append((w, s, t))
    
    edges.sort()

    cost = 0
    for edge in edges:
        w, s, t = edge
        if not uf.same(s, t):
            cost += w
            uf.union(s, t)
    print(cost)

    return

if __name__ == '__main__':
    main()

Solution (Python):
import heapq

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

visited = [False]*V
visited[0] = True
q = []
node = 0
node_cnt = 1
ans = 0

while node_cnt < V:
    for adj,w in C[node]:
        if not visited[adj]:
            heapq.heappush(q,(w,adj))
    while 1:
        weight,node = heapq.heappop(q)
        if not visited[node]:
            break
    visited[node] = True
    ans += weight
    node_cnt += 1
print(ans)

Solution (Python):
class UnionFind:
    def __init__(self, n):
        self.par = [i for i in range(n+1)]
        self.rank = [0] * (n+1)

    
    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 union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        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 same_check(self, x, y):
        return self.find(x) == self.find(y)
V, E = map(int, input().split())
X = [list(map(int, input().split())) for _ in range(E)]
X = sorted(X, key = lambda x:x[2])
UF = UnionFind(V)
ans = 0
for i in range(E):
    a, b = X[i][0]+1, X[i][1]+1
    if not UF.same_check(a, b):
        UF.union(a, b)
        ans += X[i][2]
print(ans)

Solution (Python):
from heapq import heappush, heappop

class UnionFind():
    def __init__(self, n):
        self.parents = list(range(n))

    def find(self, x):
        if self.parents[x] == x:
            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:
            self.parents[y] = x


V, E = map(int, input().split())
q = []
K = {}
ans = 0
S = UnionFind(V)

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


while len(q) > 0:
    w, s, t = heappop(q)
    if S.find(s) != S.find(t):
        ans += w
        S.union(s,t)
print(ans)

Solution (Python):
import heapq
from itertools import accumulate

v, e = map(int, input().split())
g = [[] for _ in range(v)]
for i in range(e):
    s, t, d = map(int, input().split())
    g[s].append((d, t))
    g[t].append((d, s))

visitedv = [False] * v
visitedv[0] = True

visitede = 0
candidate = []
for i in g[0]:
    heapq.heappush(candidate, i)
while len(candidate):
    
    minedge = heapq.heappop(candidate)
    if visitedv[minedge[1]]:
        continue
    c = minedge[1]
    visitedv[c] = True
    
    visitede += minedge[0]
    for i in g[c]:
        if not visitedv[i[1]]:
            heapq.heappush(candidate, i)


print(visitede)