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):
class UnionFindTree:
    def __init__(self, V):
        self.parent = [i for i in range(V)]

    def root(self, x):
        if self.parent[x] == x:
            return x
        self.parent[x] = self.root(self.parent[x])
        return self.parent[x]

    def unite(self, x, y):
        rx = self.root(x)
        ry = self.root(y)
        self.parent[rx] = ry
        return

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

class Edge:
    def __init__(self, s, t, w):
        self.s = s
        self.t = t
        self.w = w

    def __lt__(self, right):
        return self.w < right.w

def Kruscal(edges, V):
    utf = UnionFindTree(V)
    res = 0
    edges.sort()
    for e in edges:
        s = e.s
        t = e.t
        if not utf.find(e.s, e.t):
            res += e.w
            utf.unite(e.s, e.t)
    return res

def main():
    [V, E] = map(int, (raw_input()).split(" "))
    edges = [None]*E
    for i in range(E):
        [s,t,w] = map(int, (raw_input()).split(" "))
        edges[i] = Edge(s,t,w)

    print Kruscal(edges, V)

if __name__ == "__main__":
    main()

Solution (Python):
from collections import defaultdict
import heapq

vertices,edges = map(int,input().split(" "))
link = defaultdict(dict)
weight = defaultdict(dict)
way = [float("inf")] * vertices
for e in range(edges):
    source,target,w = map(int,input().split(" "))
    link[source] = link.get(source,set()) | {target}
    link[target] = link.get(target,set()) | {source}
    weight[source].update({target:w})
    weight[target].update({source:w})
queue = []
heapq.heapify(queue)
heapq.heappush(queue,[0,0])
went = [0] * vertices
now_weight = 0
way[0] = 0

while queue:
    here_weight,here = heapq.heappop(queue)
    
    if went[here]:
        continue
    went[here] = 1
    now_weight += here_weight
    min_weight,next_t = float("inf"),-1
    for c in link[here]:
        if not went[c] and way[c] > weight[here][c]:
            heapq.heappush(queue,[weight[here][c],c])
            way[c] = weight[here][c]
    
print(now_weight)

Solution (Python):
import sys
from operator import itemgetter

def solve():
    n, m = map(int, sys.stdin.readline().split())
    edges = [None] * m

    for i in range(m):
        s, t, w = map(int, sys.stdin.readline().split())
        edges[i] = (s, t, w)

    edges.sort(key=itemgetter(2), reverse=True)

    uf = UnionFind(n)

    ans = 0

    for i in range(n - 1):
        while edges:
            s, t, w = edges.pop()

            if not uf.same(s, t):
                uf.unite(s, t)
                break

        ans += w

    print(ans)

class UnionFind:
    def __init__(self, n):
        self.p = list(range(n))
        self.rank = [0] * n

    def find_root(self, x):
        if x != self.p[x]:
            self.p[x] = self.find_root(self.p[x])

        return self.p[x]

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

    def unite(self, x, y):
        u = self.find_root(x)
        v = self.find_root(y)

        if u == v: return

        if self.rank[u] < self.rank[v]:
            self.p[u] = v
        else:
            self.p[v] = u

            if self.rank[u] == self.rank[v]:
                self.rank[u] += 1

if __name__ == '__main__':
    solve()

Solution (Python):
import heapq as pq
n,E = map(int, input().split())
M = [[] for i in range(n)]
for i in range(E):
 s,t,w = map(int, input().split())
 M[s].append([t,w])
 M[t].append([s,w])

def prim():
 color = [0] * n
 d = [float("inf")] * n
 d[0] = 0
 H = []
 pq.heappush(H, [0, 0])
 while H:
  u2,u1 = pq.heappop(H)
  color[u1] = 1
  if d[u1] < u2: continue
  for v1, v2 in M[u1]:
   if color[v1] == 1: continue
   if d[v1] > v2:
    d[v1] = v2
    pq.heappush(H, [d[v1], v1])
 return sum(d)
 
print(prim())

Solution (Python):
import sys


class UnionFind():
    def __init__(self, n):
        self.n = n
        self.p = [i for i in range(n + 5)]
        self.rank = [0 for i in range(n + 5)]

    def find_set(self, x):
        if self.p[x] != x:
            self.p[x] = self.find_set(self.p[x])
        return self.p[x]

    def unite(self, x, y):
        px, py = self.find_set(x), self.find_set(y)
        if px == py:
            return
        if self.rank[px] > self.rank[py]:
            self.p[py] = px
        else:
            self.p[px] = py
            if self.rank[px] == self.rank[py]:
                self.rank[py] += 1


def main():
    sys.setrecursionlimit(int(1e5))
    nvertices, nedges = map(int, input().split())
    E = []
    uf = UnionFind(nvertices)
    for i in range(nedges):
        s, t, w = map(int, input().split())
        E.append((w, s, t))
    E.sort()

    ans = 0
    for w, s, t in E:
        if uf.find_set(s) != uf.find_set(t):
            ans += w
            uf.unite(s, t)

    print(ans)


main()

Solution (Python):
import sys
readline = sys.stdin.readline


class UnionFind:
    __slots__ = ["nodes"]

    def __init__(self, n: int) -> None:
        self.nodes = [-1]*n

    def get_root(self, x: int) -> int:
        if self.nodes[x] < 0:
            return x
        else:
            self.nodes[x] = self.get_root(self.nodes[x])
            return self.nodes[x]

    def unite(self, x: int, y: int) -> bool:
        root_x, root_y = self.get_root(x), self.get_root(y)
        if root_x != root_y:
            bigroot, smallroot = \
                (root_x, root_y) if self.nodes[root_x] < self.nodes[root_y] else (root_y, root_x)
            self.nodes[bigroot] += self.nodes[smallroot]
            self.nodes[smallroot] = bigroot
            return True
        else:
            return False


def kruskal(n: int, edges: list) -> int:
    edges.sort()
    tree = UnionFind(n)
    total = 0
    cnt = 0
    for w, s, t in edges:
        if tree.unite(s, t):
            cnt += 1
            total += w
            if cnt == n - 1:
                break

    return total


V, E = map(int, readline().split())
edges = []
append = edges.append
for _ in [None]*E:
    s, t, w = map(int, readline().split())
    append((w, s, t))
print(kruskal(V, edges))

Solution (Python):
import sys
readline = sys.stdin.readline
from operator import itemgetter
class UnionFind:
    def __init__(self, n):
        self.p = list(range(n))
        self.rank = [0] * n
    def find_root(self, x):
        if x != self.p[x]:
            self.p[x] = self.find_root(self.p[x])
        return self.p[x]
    def same(self, x, y):
        return self.find_root(x) == self.find_root(y)
    def unite(self, x, y):
        u = self.find_root(x)
        v = self.find_root(y)
        if u == v: return
        if self.rank[u] < self.rank[v]:
            self.p[u] = v
        else:
            self.p[v] = u
            if self.rank[u] == self.rank[v]:
                self.rank[u] += 1
n, m = map(int, readline().split())
edges = []
for _ in [0] * (m):
    s, t, w = map(int, readline().split())
    edges.append((s, t, w))
edges.sort(key=itemgetter(2), reverse=True)
uf = UnionFind(n)
ans = 0
for _ in [0] * (n - 1):
    while edges:
        s, t, w = edges.pop()
        if not uf.same(s, t):
            uf.unite(s, t)
            break
    ans += w
print(ans)

Solution (Python):
import sys
readline = sys.stdin.readline
from operator import itemgetter
class UnionFind:
    def __init__(self, n):
        self.p = list(range(n))
        self.rank = [0] * n
    def find_root(self, x):
        if x != self.p[x]:
            self.p[x] = self.find_root(self.p[x])
        return self.p[x]
    def same(self, x, y):
        return self.find_root(x) == self.find_root(y)
    def unite(self, x, y):
        u = self.find_root(x)
        v = self.find_root(y)
        if u == v: return
        if self.rank[u] < self.rank[v]:
            self.p[u] = v
        else:
            self.p[v] = u
            if self.rank[u] == self.rank[v]:
                self.rank[u] += 1
n, m = map(int, readline().split())
edges = [None] * m
for i in range(m):
    s, t, w = map(int, readline().split())
    edges[i] = (s, t, w)
edges.sort(key=itemgetter(2), reverse=True)
uf = UnionFind(n)
ans = 0
for _ in [0] * (n - 1):
    while edges:
        s, t, w = edges.pop()
        if not uf.same(s, t):
            uf.unite(s, t)
            break
    ans += w
print(ans)

Solution (Python):
import sys
readline = sys.stdin.readline
from operator import itemgetter
class UnionFind:
    def __init__(self, n):
        self.p = list(range(n))
        self.rank = [0] * n
    def find_root(self, x):
        if x != self.p[x]:
            self.p[x] = self.find_root(self.p[x])
        return self.p[x]
    def same(self, x, y):
        return self.find_root(x) == self.find_root(y)
    def unite(self, x, y):
        u = self.find_root(x)
        v = self.find_root(y)
        if u == v: return
        if self.rank[u] < self.rank[v]:
            self.p[u] = v
        else:
            self.p[v] = u
            if self.rank[u] == self.rank[v]:
                self.rank[u] += 1
n, m = map(int, readline().split())
edges = [tuple(map(int, readline().split())) for _ in [0] * m]
edges.sort(key=itemgetter(2), reverse=True)
uf = UnionFind(n)
ans = 0
for _ in [0] * (n - 1):
    while edges:
        s, t, w = edges.pop()
        if not uf.same(s, t):
            uf.unite(s, t)
            break
    ans += w
print(ans)

Solution (Python):
import sys
readline = sys.stdin.readline
from operator import itemgetter
class UnionFind:
    __slots__ = ['p', 'rank']
    def __init__(self, n):
        self.p = list(range(n))
        self.rank = [0] * n
    def find_root(self, x):
        if x != self.p[x]:
            self.p[x] = self.find_root(self.p[x])
        return self.p[x]
    def same(self, x, y):
        return self.find_root(x) == self.find_root(y)
    def unite(self, x, y):
        u = self.find_root(x)
        v = self.find_root(y)
        if u == v: return
        if self.rank[u] < self.rank[v]:
            self.p[u] = v
        else:
            self.p[v] = u
            if self.rank[u] == self.rank[v]:
                self.rank[u] += 1
n, m = map(int, readline().split())
edges = [tuple(map(int, readline().split())) for _ in [0] * m]
edges.sort(key=itemgetter(2), reverse=True)
uf = UnionFind(n)
ans = 0
for _ in [0] * (n - 1):
    while edges:
        s, t, w = edges.pop()
        if not uf.same(s, t):
            uf.unite(s, t)
            break
    ans += w
print(ans)

Solution (Python):
import array
import collections
import heapq
 
 
AdjacentVertex = collections.namedtuple("AdjacentVertex", "vertex cost")
INF = 2 ** 31 - 1
NO_VERTEX = -1
 
 

def compute_mst_prim(max_v, adj_list):
    
    pred = collections.defaultdict(lambda: NO_VERTEX)
    
    key = collections.defaultdict(lambda: INF)
    key[0] = 0
    
    pq = [(key[v], v) for v in range(max_v)]
    heapq.heapify(pq)
    
    in_pq = array.array("B", (True for _ in range(max_v)))
    while pq:
        _, u = heapq.heappop(pq)
        in_pq[u] = False
        for v, v_cost in adj_list[u]:
            if in_pq[v]:
                weight = v_cost
                if weight < key[v]:
                    pred[v] = u
                    key[v] = weight
                    heapq.heappush(pq, (weight, v))
                    in_pq[v] = True
    return (pred, key)
 
 
def main():
    max_v, max_e = map(int, input().split())
    adjacency_list = collections.defaultdict(set)
    for _ in range(max_e):
        s, t, w = map(int, input().split())
        adjacency_list[s].add(AdjacentVertex(t, w))
        adjacency_list[t].add(AdjacentVertex(s, w))
    (_, key) = compute_mst_prim(max_v, adjacency_list)
    print(sum(key.values()))
 
 
if __name__ == '__main__':
    main()

Solution (Python):
import array
import collections
import heapq

AdjacentVertex = collections.namedtuple("AdjacentVertex", "vertex cost")
INF = 2 ** 31 - 1
NO_VERTEX = -1
 

def compute_mst_prim(max_v, adj_list):
    
    pred = collections.defaultdict(lambda: NO_VERTEX)
    
    key = collections.defaultdict(lambda: INF)
    key[0] = 0
    
    pq = [(key[v], v) for v in range(max_v)]
    heapq.heapify(pq)
    
    in_pq = array.array("B", (True for _ in range(max_v)))
    while pq:
        _, u = heapq.heappop(pq)
        in_pq[u] = False
        for v, v_cost in adj_list[u]:
            if in_pq[v]:
                weight = v_cost
                if weight < key[v]:
                    pred[v] = u
                    key[v] = weight
                    heapq.heappush(pq, (weight, v))
                    in_pq[v] = True
    return (pred, key)

max_v, max_e = map(int, input().split())
adjacency_list = collections.defaultdict(set)
for _ in range(max_e):
    s, t, w = map(int, input().split())
    adjacency_list[s].add(AdjacentVertex(t, w))
    adjacency_list[t].add(AdjacentVertex(s, w))
(_, key) = compute_mst_prim(max_v, adjacency_list)

print(sum(key.values()))

Solution (Python):
import sys


class UnionFind:

    def __init__(self, nvertices):
        self.rank = [1] * (nvertices + 5)
        self.p = [i for i in range(nvertices + 5)]

    def find_set(self, u):
        if u != self.p[u]:
            self.p[u] = self.find_set(self.p[u])
        return self.p[u]

    def unite(self, u, v):
        x = self.find_set(u)
        y = self.find_set(v)
        if x == y:
            return
        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 is_connected(self, u, v):
        return self.find_set(u) == self.find_set(v)


def main():
    sys.setrecursionlimit(int(1e5))
    nvertices, nedges = map(int, input().split())
    edges = []
    for i in range(nedges):
        u, v, w = map(int, input().split())
        edges.append((w, u, v))

    edges.sort(key=lambda e: e[0])
    ans = 0
    uf = UnionFind(nvertices)
    for w, u, v in edges:
        if not uf.is_connected(u, v):
            uf.unite(u, v)
            ans += w

    print(ans)


main()

Solution (Python):
import heapq


def main():
    nvertices, nedges = map(int, input().split())
    Adj = [[] for i in range(nvertices)]
    for i in range(nedges):
        u, v, w = map(int, input().split())
        Adj[u].append((v, w))
        Adj[v].append((u, w))

    INF = float('inf')
    Q = [(0, 0)]
    for i in range(1, nvertices):
        Q.append((INF, i))
    heapq.heapify(Q)
    key = [INF] * nvertices
    key[0] = 0
    done = [False] * nvertices
    ans = 0
    while Q:
        val, u = heapq.heappop(Q)
        if val > key[u]:
            continue
        done[u] = True
        ans += val
        for v, w in Adj[u]:
            if not done[v] and w < key[v]:
                key[v] = w
                heapq.heappush(Q, (w, v))

    print(ans)


main()

Solution (Python):
from collections import defaultdict
from heapq import heappush, heappop
INF = 9999999999999999999999999999

def spanning_tree(G):
  n = len(G)
  T = {}
  added = set([0])
  heap = []
  for v in G[0]:
    heappush(heap, (G[0][v], (0, v)))
  while len(added) < n:
    while True:
      c, e = heappop(heap)
      if e[1] not in added:
        break
    T[e] = c
    added.add(e[1])
    for v in G[e[1]]:
      heappush(heap, (G[e[1]][v], (e[1], v)))

  return T


G = {}

n, m = [int(v) for v in input().strip().split(' ')]
for i in range(n):
  G[i] = {}
for _ in range(m):
  s, t, c = [int(v) for v in input().strip().split(' ')]
  G[s][t] = c
  G[t][s] = c

if m == 0:
  print(0)
  exit()

T = spanning_tree(G)

s = 0
for e in T:
  s += T[e]

print(s)

Solution (Python):
import heapq
from collections import defaultdict

INF = float('inf')


V, E = map(int, input().split())
Adj_list = defaultdict(set)

for i in range(E):
    s, t, w = map(int, input().split())
    Adj_list[s].add((t, w))
    Adj_list[t].add((s, w))
    
def prim(x):
    d = [INF] * x
    d[0] = 0
    isVisited = [False] * x
    hq = [(0,0)] 
    
    while hq:
        u = heapq.heappop(hq)[1]
        isVisited[u] = True
        
        for v, c in Adj_list[u]:
            if not isVisited[v] and d[v] > c:
                d[v] = c
                heapq.heappush(hq, (c, v))
    return sum(d)

print(prim(V))

Solution (Python):

"""
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=GRL_2_A&lang=jp

"""
import sys
from sys import stdin
input = stdin.readline
from collections import namedtuple


class DisjointSet(object):
    def __init__(self, size):
        self.rank = []
        self.p = []
        for i in range(size):
            self.makeSet(i)

    def makeSet(self, x):
        self.p.insert(x, x)
        self.rank.insert(x, 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 kruskal(V, E, es):
    es.sort(key=lambda x: x.c)
    uf = DisjointSet(V)
    res = 0

    for i in range(E):
        e = es[i]
        if not uf.same(e.u, e.v):
            uf.unite(e.u, e.v)
            res += e.c
    return res

edge = namedtuple('edge', ['u', 'v', 'c'])
def main(args):
    V, E = map(int, input().split())
    es = []
    for _ in range(E):
        s, t, w = map(int, input().split())
        es.append(edge(s, t, w))

    result = kruskal(V, E, es)
    print(result)



if __name__ == '__main__':
    main(sys.argv[1:])

Solution (Python):

from operator import itemgetter

import sys
sys.setrecursionlimit(10000)

def inpl(): return tuple(map(int, input().split()))

V, E = inpl()
edges = []
graph = [[] for _ in range(V)]  
total_cost = 0

for _ in range(E):
    edges.append(inpl())

gw = itemgetter(2)
edges = sorted(edges, key = gw)

tree = [[-1, 1]  for _ in range(V)] 

def find(i):
    if tree[i][0] == -1:
        group = i
    else:
        group = find(tree[i][0])    
    return group
 
def unite(x, y):
    px = find(x)
    py = find(y)
     
    if tree[px][1] == tree[py][1]: 
        tree[py][0] = px
        tree[px][1] += 1
    else:
        if tree[px][1] < tree[py][1]:
            px, py = py, px
        tree[py][0] = px
 
for s, t, w in edges:
    if find(s) != find(t):
        unite(s, t)
        total_cost += w
        graph[s].append([t, w])
        graph[t].append([s, w])

print(total_cost)

Solution (Python):
from collections import defaultdict
import heapq
vertices, edges = (int(n) for n in input().split(" "))
conn = defaultdict(set)
weight = defaultdict(dict)
for i in range(edges):
    v1, v2, w = (int(n) for n in input().split(" "))
    conn[v1] |= {v2}
    conn[v2] |= {v1}
    weight[v1][v2] = w
    weight[v2][v1] = w

queue = []
heapq.heapify(queue)
heapq.heappush(queue, [0,0])
went = set()
went_vertices = 0
answer_weight = 0
while went_vertices < vertices:
    here_weight, here_v = heapq.heappop(queue)
    if here_v in went:
        continue
    went |= {here_v}
    for c in conn[here_v]:
        if c not in went:
            heapq.heappush(queue,[weight[here_v][c], c])
    answer_weight += here_weight
    went_vertices += 1
print(answer_weight)

Solution (Python):
rank = {}
p = {}

class Edge: pass

def makeSet(x):
    p[x] = x
    rank[x] = 0
 
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 union(x, y):
    link(findSet(x), findSet(y))
     
def findSet(x):
    if  x != p[x]: p[x] = findSet(p[x])
    return p[x]
     
def isSameSet(x, y):
    return findSet(x) == findSet(y)
 
V, E = map(int, input().split())
el = []

for i in range(E):
    s,t,w = map(int, input().split())
    e=Edge()
    e.source = s
    e.target = t
    e.weight = w
    el.append(e)

def kruskal(v, e):
    e = sorted(e, key=lambda x: x.weight)
    for i in v:
        makeSet(i)
    K = []
    for i in e:
        if findSet(i.source) != findSet(i.target):
            union(i.source, i.target)
            K.append(i.weight)
    return K

print(sum(kruskal(range(V), el)))

Solution (Python):

from operator import itemgetter


class DisjointSet():
    def __init__(self, size):
        self.size = size
        self.rank = [None] * size
        self.parents = [None] * size
        for i in range(size):
            self.makeSet(i)

    def makeSet(self, x):
        self.parents[x] = x
        self.rank[x] = 0

    def findSet(self, x):
        if x != self.parents[x]:
            self.parents[x] = self.findSet(self.parents[x])
        return self.parents[x]

    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.parents[y] = x
        else:
            self.parents[x] = y
            if self.rank[x] == self.rank[y]:
                self.rank[y] += 1


if __name__ == '__main__':

    n, m = [int(s) for s in input().split()]
    E = []
    for _ in range(m):
        E.append([int(s) for s in input().split(" ")])

    def kruskal(n, E):
        E = sorted(E, key=itemgetter(2))
        totalCost = 0
        S = DisjointSet(n)
        

        for s, t, w in E:
            if S.findSet(s) != S.findSet(t):
                S.unite(s, t)
                
                totalCost += w

        return totalCost

    print(kruskal(n, E))

Solution (Python):
import array, collections

Edge = collections.namedtuple("Edge", "start end weight")

class UnionFind(object):
    def __init__(self, number_of_nodes):
        self.par = array.array("L", range(number_of_nodes))
        self.rank = array.array("L", (0 for _ in range(number_of_nodes)))

    def root(self, node):
        if self.par[node] == node:
            return node
        else:
            r = self.root(self.par[node])
            self.par[node] = r
            return r

    def in_the_same_set(self, node1, node2):
        return self.root(node1) == self.root(node2)

    def unite(self, node1, node2):
        x = self.root(node1)
        y = self.root(node2)
        if x == y:
            pass
        elif 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 compute_mst_kruskal(v_size, edges):
    edges.sort(key=lambda e: e.weight)
    uf = UnionFind(v_size)
    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


edges = []
v, e = map(int, input().split())
for _ in range(e):
  edges.append(Edge(*map(int, input().split())))
print(sum(e.weight for e in compute_mst_kruskal(v, edges)))

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

from collections import deque

q = deque(sorted(data, key=lambda x: x[2]))


parent = [i for i in range(v)]
rank = [0 for i in range(v)]


def find(x):
    if parent[x] == x:
        return x
    else:
        parent[x] = find(parent[x])
        return parent[x]

def judge(a, b):
    a_parent = find(a)
    b_parent = find(b)
    if a_parent == b_parent:
        return True
    else:
        return False

def merge(a, b):
    a_parent = find(a)
    b_parent = find(b)
    if a_parent == b_parent:
        return
    else:
        if rank[a_parent] > rank[b_parent]:
            parent[b_parent] = a_parent
        elif rank[a_parent] < rank[b_parent]:
            parent[a_parent] = b_parent
        else:
            parent[a_parent] = b_parent
            rank[b_parent] += 1




ans = 0
while len(q) > 0:
    a = q.popleft()
    if not judge(a[0], a[1]):
        merge(a[0], a[1])
        ans += a[2]

print(ans)

Solution (Python):
import sys
import collections

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

Edge = collections.namedtuple('Edge', ['s', 't', 'cost'])
    
V, E = map(int, sys.stdin.readline().split())
edges = sorted([Edge(*map(int, line.split())) for line in sys.stdin], key=lambda e: e.cost)
uf = UnionFind(V)
min_cost = 0
for edge in edges:
    if not uf.are_same(edge.s, edge.t):
        uf.union(edge.s, edge.t)
        min_cost += edge.cost
print(min_cost)

Solution (Python):
import sys
import collections
import heapq
import math

Edge = collections.namedtuple('Edge', ['s', 't', 'cost'])
    
V, E = map(int, sys.stdin.readline().split())
edges = collections.defaultdict(list)
for line in sys.stdin:
    e = Edge(*map(int, line.split()))
    edges[e.s].append(e)
    edges[e.t].append(Edge(e.t, e.s, e.cost))

heap = [(e.cost, e) for e in edges[0]]
heapq.heapify(heap)
nodes = {0}
min_cost = 0
while heap:
    _, edge = heapq.heappop(heap)
    if edge.t not in nodes:
        nodes.add(edge.t)
        for e in edges[edge.t]:
            heapq.heappush(heap, (e.cost, e))
        min_cost += edge.cost
print(min_cost)

Solution (Python):
class Edge:
    def __init__(self, s, t, w):
        self.s = s
        self.t = t
        self.w = w

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


def link(x, y):
    if r[x] > r[y]:
        p[y] = x

    else:
        p[x] = y
        if r[x] == r[y]: r[y] = r[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)



if __name__ == '__main__':
    p, r = [], []

    n_V, n_E = map(int, input().split())

    for i in range(n_V):
        p.append(i)
        r.append(0)

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

    Es.sort(key=lambda e : e.w)

    sum_w = 0
    for e in Es:
        if not same(e.s, e.t):
            union(e.s, e.t)
            sum_w += e.w

    print(sum_w)

Solution (Python):
class Vertex:
    def __init__(self, p):
        self.p = p
        self.r = 0


class Edge:
    def __init__(self, s, t, w):
        self.s = s
        self.t = t
        self.w = w


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


def link(x, y):
    if V[x].r > V[y].r:
        V[y].p = x

    else:
        V[x].p = y
        if V[x].r == V[y].r: V[y].r = V[y].r + 1


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

    return V[x].p


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



if __name__ == '__main__':
    n_V, n_E = map(int, input().split())

    
    V = []
    for i in range(n_V):
        V.append(Vertex(i))

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

    
    E.sort(key=lambda e : e.w)

    
    sum_w = 0
    for e in E:
        if not same(e.s, e.t):
            union(e.s, e.t)
            sum_w += e.w

    print(sum_w)

Solution (Python):

p = []
rank = []
edge = []
cost = 0

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

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

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

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

def same(x, y):
    if findSet(x) == findSet(y):
        return 1
    else:
        return 0   

[v, e] = list(map(int, input().split()))
for i in range(v):
    makeSet(i)

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

edge.sort()

while v > 1:
    min = edge.pop(0)
    if not same(min[1], min[2]):
        union(min[1], min[2])
        cost += min[0]
        v -= 1

print(cost)

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

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

        self.par[y] = x;
        self.sizes[x] += self.sizes[y]

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

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

class Edge:
    def __init__(self, s, t, w):
        self.s = s
        self.t = t
        self.w = w
    def __lt__(self, other):
        return self.w < other.w

def kruskal(edges, n):
    edges = sorted(edges)
    uf = UnionFind(n)
    min_cost = 0

    for edge in edges:
        if not uf.same(edge.s, edge.t):
            min_cost += edge.w
            uf.unite(edge.s, edge.t)

    return min_cost

v, e = map(int, input().split())
es = []
for i in range(e):
    s, t, w = map(int, input().split())
    es.append(Edge(s, t, w))
print(kruskal(es, v))

Solution (Python):
"""
Kruskal
"""
from heapq import heappop, heappush

v_num, e_num = map(int, input().split())
pair_lst = [i for i in range(v_num)]
que = []
for _ in range(e_num):
  s, t, w = map(int, input().split())
  heappush(que, (w, s, t))

def find(x):
  if x == pair_lst[x]:
    return x
  else:
    tmp = find(pair_lst[x])
    pair_lst[x] = tmp
    return tmp

length_sum = 0
while que:
  w, s, t = heappop(que)
  root_s = find(s)
  root_t = find(t)
  if root_s != root_t:
    pair_lst[root_s] = root_t
    length_sum += w

print(length_sum)