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):
from heapq import heapify
from heapq import heappop
from heapq import heappush
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())
V,E = map(int,input().split())
uf = UnionFind(V)
hq = []
heapify(hq)
for i in range(E):
    s,t,w = map(int,input().split())
    heappush(hq,(w,s,t))
ans = 0 
while len(hq) != 0:
    w,s,t = heappop(hq)
    if not uf.same(s,t):
        ans += w
        uf.union(s,t)
    else:
        continue
print(ans)

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

v, e = map(int,input().split())
road = []
for i in range(e):
    a, b, c = list(map(int,input().split()))
    road.append((a,b,c))
road.sort(key = lambda x: x[2])


uf = UnionFind(v)
cost = 0
cnt = 0
for i in range(e):
    a = road[i][0]
    b = road[i][1]
    c = road[i][2]
    if uf.same(a,b) == False:
        uf.union(a,b)
        cost += c
        cnt += 1
        if cnt == v-1:
            break

print(cost)

Solution (Python):
class UnionFind:
    def __init__(self,n):
        self.n=n
        self.parents=[-1]*n
        self.rank=[0]*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.rank[x]<self.rank[y]:
            self.parents[y]+=self.parents[x]
            self.parents[x]=y
        else:
            self.parents[x]+=self.parents[y]
            self.parents[y]=x

            if self.rank[x]==self.rank[y]:
                self.rank[x]+=1

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

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

    def group_count(self):
        count=0
        for e in self.parents:
            if e<0: count+=1
        return count

def kruskal(n,edges):
    u=UnionFind(n)
    ans=0
    for x in edges:
        s,t,w=x
        if u.are_same(s,t)==False:
            u.union(s,t)
            ans+=w

    return ans

from sys import stdin
def main():
    
    readline=stdin.readline
    v,e=map(int,readline().split())
    edges=[list(map(int,readline().split())) for _ in range(e)]
    edges.sort(key=lambda x:x[2])
    print(kruskal(v,edges))

if __name__=="__main__":
    main()

Solution (Python):









import sys,collections
sys.setrecursionlimit(10000)

INF = float("inf")

V,E = map(int,sys.stdin.readline().split())
stw = tuple(tuple(map(int,sys.stdin.readline().rstrip().split())) for _ in range(E)) 







wst = [[w,s,t] for s,t,w in stw]
wst.sort()

parents = list(range(V))
def find(x):
  while parents[x] != x:
    x = parents[x]
    parents[x] = parents[parents[x]]
  return x

def union(s,t):
  sp = find(s)
  tp = find(t)
  if sp == tp:
    pass
  elif sp < tp:
    parents[sp] = tp
  else:
    parents[tp] = sp

INF = float("inf")
ret = 0
for w,s,t in wst:
    if find(s) != find(t):
        union(s,t)
        ret += w
print(ret)

Solution (Python):
class unionfind:
    sz = 0
    par = []
    def __init__(self, n):
        self.sz = n
        for i in range(n):
            self.par.append(-1)

    def find(self, a):
        if self.par[a]<0: return a
        self.par[a] = self.find(self.par[a])
        return self.par[a]
    
    def size(self, a):
        a = self.find(a)
        return -self.par[a]
    
    def same(self, a,b):
        return self.find(a) == self.find(b)

    def unite(self, a,b):
        a = self.find(a)
        b = self.find(b)
        if self.same(a,b): return False
        if self.size(a) < self.size(b):
            a,b=b,a
        self.par[a] += self.par[b]
        self.par[b] = a
        return True

n,m = map(int,input().split())
g = []
for i in range(m):
    s,t,w = map(int,input().split())
    g.append([w,s,t])
g = sorted(g)
ans = 0
uni = unionfind(n)
for c,i,j in g:
    if uni.unite(i,j): ans += c
print(ans)

Solution (Python):
import heapq

n,e=map(int,input().split())
G=[[] for _ in range(n)]
for index in range(e):
    s,t,w=map(int,input().split())
    
    G[s].append([w,t])
    G[t].append([w,s])


def prim_heap():
    used = [True] * n 
    edgelist = []
    for e in G[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 G[v]:
            if used[e[1]]:
                heapq.heappush(edgelist,e)
        res += minedge[0]
    return res

ans=prim_heap()
print(ans)

Solution (Python):
class UnionFind:
    def __init__(self, V):
        self.group = [i for i in range(V)]
        self.rank = [0] * V

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

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

        if x == y:
            return
        
        if self.rank[x] < self.rank[y]:
            self.group[x] = y
        else:
            self.group[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

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

class Edge:
    def __init__(self, FROM, TO, WEIGHT):
        self.FROM = FROM
        self.TO = TO
        self.WEIGHT = WEIGHT

    def __lt__(self, arg):
        return self.WEIGHT < arg.WEIGHT

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

UF = UnionFind(V)

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

ans = 0
for i in range(E):
    if UF.is_same_group(G[i].FROM, G[i].TO):
        continue
    UF.unite(G[i].FROM, G[i].TO)
    ans += G[i].WEIGHT

print(ans)

Solution (Python):
import heapq

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

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

    edges[s-1].append([w, t-1])
    edges[t-1].append([w, s-1])


def prim(n, w, edges):
    used = [True] * n 
    edgelist = []
    for e in edges[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 edges[v]:
            if used[e[1]]:
                heapq.heappush(edgelist,e)
        res += minedge[0]
    return res

print(prim(V, E, edges))

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

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

Edges.sort(key=lambda x:x[2])
F=UnionFind(V)
cost=0
for e in Edges:
    if F.same(e[0],e[1]):
        continue
    F.union(e[0],e[1])
    cost+=e[2]
print(cost)

Solution (Python):
import sys, heapq
input = lambda: sys.stdin.readline().rstrip() 
sys.setrecursionlimit(10**7)
INF = 10**10
def I(): return int(input())
def F(): return float(input())
def S(): return input()
def LI(): return [int(x) for x in input().split()]
def LI_(): return [int(x)-1 for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LS(): return 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 same(self, x, y):
        return self.find(x) == self.find(y)

def kruskal(es, V):
    es.sort(key=lambda x:x[2])
    uf = UnionFind(V)
    res = 0
    for e in es:
        if not uf.same(e[0], e[1]):
            uf.union(e[0], e[1])
            res += e[2]
    return res

def resolve():
    V, E = LI()
    es = [[[]] for _ in range(E)]
    for i in range(E):
        s, t, w = LI()
        es[i] = [s, t, w]

    print(kruskal(es, V))

if __name__ == '__main__':
    resolve()

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

    def nums(self,x):
        return abs(self.parents[self.find(x)])

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

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

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

N, M = map(int, input().split())
edges = []*M
for i in range(M):
    a,b,w = map(int, input().split())
    edges.append((w,a,b))

edges.sort()

uf = UnionFind(N)
ans = 0
for i in range(M):
    u,x,y = edges[i]
    if not uf.same(x,y):
        uf.union(x,y)
        ans += u
print(ans)

Solution (Python):

import sys
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines

class UnionFind:
    def __init__(self, n):
        
        self.par = [i for i in range(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.find(self.par[x])
  
    
    def unite(self, x, y):
        
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        
        if self.size[x] < self.size[y]:
            self.par[x] = y
            self.size[y] += self.size[x]
        else:
            self.par[y] = x
            self.size[x] += self.size[y]
           
    
    def is_same(self, x, y):
        return self.find(x) == self.find(y)
    
    
    def get_size(self, x):
        return self.size[self.find(x)]
    
    
    def group_sum(self):
        c = 0
        for i in range(len(self.par)):
            if self.find(i) == i:
                c += 1
        return c


def main():
    V,E,*stw = map(int, read().split())

    Edges = []
    for s, t, w in zip(*[iter(stw)]*3):
        Edges.append((s, t, w))
    
    Edges.sort(key=lambda x: x[2])
    
    uf = UnionFind(V)
    ans = 0
    for s, t, w in Edges:
        if uf.is_same(s, t):
            continue
        else:
            ans += w
            uf.unite(s, t)

    print(ans)
   

if __name__ == "__main__":
    main()

Solution (Python):
from heapq import heappop, heappush
v, e = map(int, input().split())
G = [[] for _ in range(v)]
for _ in range(e):
    s, t, w = map(int, input().split())
    G[s].append((w,t))
    G[t].append((w,s))
been = [0]*v
ans = 0

queue = []
a = (0,0)
heappush(queue,a)
been[0] = 1

while sum(been) != v:
    while len(queue):
        a = heappop(queue)
        if been[a[1]] == 0:
            been[a[1]] = 1
            break
    
    ans += a[0]
    
    for nex in G[a[1]]:
        heappush(queue, (nex[0], nex[1]))
print(ans)

Solution (Python):
import heapq
v,e=map(int,input().split())
edge=[]
for i in range(e):
  s,t,w=map(int,input().split())
  edge.append([w,s,t])
heapq.heapify(edge)
class UnionFind:
  def __init__(self,n):
    self.n=n
    self.r=[i for i in range(n)]
    self.rank=[1 for i in range(n)]
    self.cost=0
  def find(self,x):
    if x==self.r[x]:
      return x
    else:
      self.r[x]=self.find(self.r[x])
      return self.r[x]
  def union(self,x,y,c):
    rx=self.find(x)
    ry=self.find(y)
    if rx==ry:
      return
    if self.rank[ry]>self.rank[rx]:
      rx,ry=ry,rx
    self.r[ry]=rx
    self.rank[rx]+=self.rank[ry]
    self.cost+=c
uf=UnionFind(v)
while edge:
  path=heapq.heappop(edge)
  if uf.find(path[1])==uf.find(path[2]):
    continue
  uf.union(path[1],path[2],path[0])
print(uf.cost)

Solution (Python):


from pprint import pprint

INF = float('inf')

n_nodes, m_edges = map(int, input().split())
edges = []
for _ in range(m_edges):
    u, v, w = map(int, input().split())
    edges.append([u, v, w])


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




def find_root(v, parents):
    if v == parents[v]:
        return v
    parents[v] = find_root(parents[v], parents)
    return parents[v]


def has_same_root(u, v, parents):
    return find_root(u, parents) == find_root(v, parents)


def unite(u, v, parents):
    root_u = find_root(u, parents)
    root_v = find_root(v, parents)
    parents[root_u] = root_v
    return parents


parents = [i for i in range(n_nodes)]
res = 0
for u, v, w in edges_sorted:
    if not has_same_root(u, v, parents):
        res += w
        parents = unite(u, v, parents)
print(res)

Solution (Python):
import heapq
def set_heapq(que, edge, used, v, add_dist=0):
    '''
    確定地点vからつながる辺を全てqueに設定し、返却する

    Parameters
    que : heapque(touple or list)
        辺を管理するキュー (距離、次の行き先)のtopuleまたはlistにて管理
    edge : list
        全ての辺を格納する二次元のリスト edge[0]にてノード0から伸びる辺であることを表し、
        edge[0] → [距離、次の行き先] を表すlistが格納されている
    v : int
        グラフ上のノード ダイクストラでは確定したノードがvにあたる
    add_dist : int
        確定した地点に足し合わせる距離 スタート地点以外では何かしらの値が追加されることになる

    Returns
    que : heapque(touple or list)
        引数queにvからつながる辺を追加したキュー
    '''
    for a,b in edge[v]:
        if used[b]:
            heapq.heappush(que,(a+add_dist,b))
    return que

def prim_heap(edge, n):
    '''
    プリム法で最小全域木を求める

    Parameters
    edge : list
        全ての辺を格納する二次元のリスト edge[0]にてノード0から伸びる辺であることを表し、
        edge[0] → [距離、次の行き先] を表すlistが格納されている
    
    Returns
    res : int
        最小全域木の全ての辺のコストの総和
    '''
    used = [True] * n 
    edgelist = []
    edgelist = set_heapq(edgelist, edge, used, 0)
    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
        edgelist = set_heapq(edgelist, edge, used, v)
        res += minedge[0]
    return res

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

print(prim_heap(edge, V))

Solution (Python):
from heapq import heappop,heappush
inf = float("inf")
white = 0; gray = 1; black =2

def prim():
    mindist[0] = 0 
    PQ = [(0,0)]
    while PQ:
        minw,s = heappop(PQ)
        color[s] = black
        if mindist[s] < minw: continue
        for t,w in G[s]:
            if color[t] == black: continue
            if w < mindist[t]:
                mindist[t] = w
                color[t] = gray
                heappush(PQ,(w,t))
    return sum(mindist)

V,E = map(int,input().split())
G = [[] for _ in range(V)]
for _ in range(E):
    s,t,w = map(int,input().split())
    G[s].append((t,w))
    G[t].append((s,w))
color = [white]*V
mindist = [inf]*V
print(prim())

Solution (Python):
import sys
import copy
import heapq
from collections import deque


INF = sys.maxsize



def main():
    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())

    v, e = map(int, input().split())
    tree = UnionFind(v)

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

    edges.sort()

    ans = 0
    for d,s,t in edges:
        if tree.same(s,t):
            continue
        tree.union(s,t)
        ans += d

    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
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()


def find(x):
    if par[x] < 0:
        return x
    else:
        par[x] = find(par[x])
        return par[x]



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

    if x == y:
        return False
    else:
        
        if par[x] > par[y]:
            x, y = y, x
        par[x] += par[y]
        par[y] = x
        return True



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



def size(x):
    return -par[find(x)]



par = [-1]*V
ans = 0
for e in edges:
    if same(e[1],e[2]):
        continue
    ans += e[0]
    unite(e[1],e[2])
print(ans)

Solution (Python):
def find(x):
    if(par[x]==x):
        return x
    else:
        par[x]=find(par[x])
        return par[x]
def union(a,b):
    a=find(a)
    b=find(b)
    if(a==b):
        return 0
    else:
        if rank[a]>rank[b]:
            par[b]=a
        else:
            par[a]=b
            if rank[a]==rank[b]:
                rank[b]+=1
def same(a,b):
    return find(a)==find(b)
def Kruskal():
    cost=0
    Edge.sort(key=lambda x:x[2])
    for i in range(E):
        f,t,c=Edge[i]
        if(not same(f,t)):
            union(f,t)
            cost+=c
    return cost

N,E=map(int,input().split())
par=[i for i in range(N)]
rank=[0 for _ in range(N)]
Edge=[]
for i in range(E):
    s,t,w=map(int,input().split())
    Edge.append([s,t,w])
res=Kruskal()
print(res)

Solution (Python):
from collections import namedtuple


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

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

  def unite(self, a, b):
    a = self.find(a)
    b = self.find(b)  
    if self.size[a] < self.size[b]:
      a, b = b, a
    self.par[b] = a
    self.size[a] += self.size[b]

  def size_of(self, a):
    return self.size[self.find(a)]

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

Edge = namedtuple('Edge', 'w s t')

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

for _ in range(E):
  s, t, w = map(int, input().split())
  edges.append(Edge(w, s, t))

edges.sort()

u = UnionFind(V)
cost = 0

for w, s, t in edges:
  if u.is_same(s, t):
    continue
  u.unite(s, t)
  cost += w

print(cost)

Solution (Python):
from collections import defaultdict

class Graph:

    def __init__(self,vertices):
        self.V = vertices
        self.graph = []

    def addEdge(self,s,t,w):
        self.graph.append([s,t,w])

    def find(self, parent, i):
        if(parent[i] == i):
            return i
        return self.find(parent, parent[i])

    def union(self, parent, rank, x, y):
        xroot = self.find(parent, x)
        yroot = self.find(parent, y)

        if rank[xroot] < rank[yroot]:
            parent[xroot] = yroot
        elif rank[xroot] > rank[yroot]:
            parent[yroot] = xroot

        else :
            parent[yroot] = xroot
            rank[xroot] += 1

    def KruskalMST(self):
        sum = 0
        result = []
        i = 0
        e = 0

        self.graph = sorted(self.graph, key=lambda item:item[2])
        parent = []
        rank = []
        for node in range(self.V):
            parent.append(node)
            rank.append(0)

        while e < self.V - 1:
            s, t, w = self.graph[i]
            i+=1
            x = self.find(parent, s)
            y = self.find(parent, t)

            if x != y:
                e = e + 1
                result.append([s, t, w])
                self.union(parent, rank, x, y)

        for s,t,weight in result:
            sum +=  weight

        print(sum)

if __name__ == "__main__":
    V, E = (int(z) for z in input().split())
    g = Graph(V)

    for i in range(E):
        s, t, w = (int(z) for z in input().split())
        g.addEdge(s, t, w)

    g.KruskalMST()

Solution (Python):

class UnionFind:

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

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

    
    def union(self, x, y):
        
        x = self.findSet(x)
        y = self.findSet(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.findSet(x) == self.findSet(y)



def compute_mst_kruskal(v, edges):
    
    
    edges = sorted(edges,key=lambda x: x[2])
    
    uf = UnionFind(v)
    mst = []

    
    """
    for edge in edges:
        
        if not uf.in_the_same_set(edge.start, edge.end):
            uf.unite(edge.start, edge.end)
            mst.append(edge)
    return mst
    """
    i = 0
    
    while i < len(edges):
        
        edge = edges[i]

        """
        start : 選択された辺の始点
        end   : 選択された辺の終点
        無向グラフなのでstart,end自体に大きな意味はない
        """
        start = edges[i][0]
        end   = edges[i][1]

        
        if not uf.same_check(start, end):
            
            uf.union(start,end)
            mst.append(edge)
        i = i + 1
    return mst

def buble_sort(tdlist):
    i=0
    while i < len(tdlist)-1:
        if tdlist[i][2] > tdlist[i+1][2]:
            tmp = tdlist[i]
            tdlist[i] = tdlist[i+1]
            tdlist[i+1] = tmp
            i = -1
        i = i + 1

    
    return tdlist


def main():
    
    p = []  
    v, e = map(int, input().split())
    
    
    
    i = 0
    while i < e:
        try:
            p.append(list(map(int, input().split())))
            i = i + 1
        except:
            break;

    mst = compute_mst_kruskal(v, p)
    


    i = 0
    total_weight = 0
    while i < len(mst):
        total_weight = total_weight + mst[i][2]
        i = i + 1
    print(total_weight)



if __name__ == '__main__':
    main()

Solution (Python):
class UnionFind:
    
    
    def __init__(self, n):
        self.N = n
        self.parent = [i for i in range(n)]
        self.rank = [0 for _ in range(n)]

    
    def root(self, x):
        visited_nodes = []
        while True:
            p = self.parent[x]
            if p == x:
                
                for node in visited_nodes:
                    self.parent[node] = x
                return x
            else:
                visited_nodes.append(x)
                x = p

    
    def unite(self, x, y):
        if not self.root(x) == self.root(y):
            if self.rank[x] > self.rank[y]:
                self.parent[self.root(y)] = self.root(x)
            else:
                self.parent[self.root(x)] = self.root(y)
                if self.rank[x] == self.rank[y]:
                    self.rank[self.root(y)] += 1

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

    
    def printDebugInfo(self):
        print([self.root(i) for i in range(self.N)])


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

tree = UnionFind(V)

weight = 0
counter = 0
for edge in edges:
    if tree.ifSame(edge[1], edge[2]):
        continue
    else:
        tree.unite(edge[1], edge[2])
        weight += edge[0]
        counter += 1
    if counter == V-1:
        break

print(weight)

Solution (Python):
import heapq

def makeSet(x):
    p[x] = x
    rank[x] = 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] += 1

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



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

p = [0]*v
rank = [0]*v
for x in range(v):
    makeSet(x)

S = []
ans = 0
for _ in range(e):
    s,t,w = map(int, input().split())
    heapq.heappush(S, [w, s, t])
    
while S:
    w,s,t = heapq.heappop(S)
    if findSet(s) != findSet(t):
        union(s,t)
        ans += w
print(ans)

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

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

for i in range(E):
    if not uf.same(G[i][1], G[i][2]):
        ans += G[i][0]
        uf.union(G[i][1], G[i][2])

print(ans)

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