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

Solution (Python):
import sys
import heapq


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 find_set(x):
    if x != p[x]:
        p[x] = find_set(p[x])
    return p[x]


def unite(x, y):
    link(find_set(x), find_set(y))


def same(x, y):
    x = find_set(x)
    y = find_set(y)
    if x == y:
        return True
    else:
        return False


h = []

line = sys.stdin.readline()
v, e = map(int, line.split())
p = [i for i in range(v)]
rank = [0 for _ in range(v)]

for i in range(e):
    line = sys.stdin.readline()
    s, t, w = map(int, line.split())
    heapq.heappush(h, (w, s, t))

s = 0
for i in range(e):
    elm = heapq.heappop(h)
    if not same(elm[1], elm[2]):
        s = s + elm[0]
        unite(elm[1], elm[2])

print(s)

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

    def add(self, u, v, d):
        """
        :param u: 始点
        :param v: 終点
        :param d: コスト
        """
        self.edges.append([u, v, d])

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

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

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

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

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

V, E = map(int, input().split())
graph = Kruskal_UnionFind(V)
for i in range(E):
    s, t, w = map(int, input().split())
    graph.add(s, t, w)

print(graph.Kruskal())

Solution (Python):
import heapq

v, e = map(int, input().split())
edges = []
for i in range(e):
    s, t, w = map(int, input().split())
    heapq.heappush(edges, (w, (s, t)))


class Node():
    def __init__(self, id):
        self.id = id
        self.p = self
        self.rank = 0


class DisjointSet():
    def __init__(self, n):
        self.nodes = {}
        for i in range(n):
            self.makeSet(i)

    def makeSet(self, i):
        self.nodes[i] = Node(i)

    def findSet(self, x):
        if x.p is not x:
            x.p = self.findSet(x.p)
        return x.p

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

    def bool(self, x, y):
        return self.findSet(x) == self.findSet(y)


def kruskal(v, edges):
    S = DisjointSet(v)
    K = []

    while len(edges):
        w, edge = heapq.heappop(edges)
        
        x, y = S.nodes[edge[0]], S.nodes[edge[1]]
        if not S.bool(x, y):
            S.unite(x, y)
            K.append((edge, w))
    return K


K = kruskal(v, edges)

print(sum(map(lambda x: x[1], K)))

Solution (Python):
class UnionFindTree:
    '''
    Union Find Tree
    '''

    def __init__(self):
        self.p = {}
        self.rank = {}

    def make(self, x):
        self.p[x] = x
        self.rank[x] = 0

    def find(self, x):
        if x in self.p:
            if self.p[x] != x:
                
                self.p[x] = self.find(self.p[x])
            return self.p[x]
        return None

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

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

    def _unite(self, x, y):
        if self.rank[x] < self.rank[y]:
            self.p[x] = y
        else:
            self.p[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1


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

'''
クラスカルのアルゴリズム
最小全域木の総重み
辺をソートし、UnionFindTreeで同じ集合に属する辺を作らずに集合を構築
'''
e.sort()
uft = UnionFindTree()
for i in range(V):
    uft.make(i)

ans = 0

for w, s, t in e:
    if not uft.same(s, t):
        uft.unite(s, t)
        ans += w

print(ans)

Solution (Python):
class UnionFind:
    def __init__(self, v_count: int):
        self.par = [-1]*v_count 
        for i in range(v_count):
            self.par[i] = i  
    
    def root(self, x: int) -> int:
        """根を求める"""
        if self.par[x] == x: 
            return x
        else:
            self.par[x] = self.root(self.par[x]) 
            return self.par[x]
    
    def is_same(self, x:int, y:int)->bool:
        """x と y が同じ集合に属するか否か"""
        return self.root(x)==self.root(y)
    
    def unite(self, x:int, y:int):
        """x と y の属する集合を併合"""
        x = self.root(x)
        y = self.root(y)
        if x == y: return
        self.par[x] = y

def kruskal(v_count: int) -> int:
    """O(|E| log|V|)
    return the minimum cost of Spanning Tree"""
    global edges 
    uf = UnionFind(v_count)
    
    cost = 0
    for w,s,t in sorted(edges): 
        if not uf.is_same(s, t):
            uf.unite(s, t)
            cost += w
    return cost


if __name__ == "__main__":
    V,E = map(int, input().split())
    edges = []
    for _ in range(E):
        s,t,w = map(int, input().split())
        edges.append((w,s,t))
    ans = kruskal(V)
    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):




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

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

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




class kruskal():
    def __init__(self, V, E):
        self.V = V
        self.E = E
        self.E.sort(key=lambda x: x[2]) 

    def weight(self):
        UF = UnionFind(len(V)) 
        res = 0
        for i in range(len(self.E)):
            e = self.E[i]
            
            if (UF.same(e[0], e[1])) == False:
                UF.unite(e[0], e[1])
                res += e[2]
                
        return res

    def edge(self):
        UF = UnionFind(len(V)) 
        res_E = []
        for i in range(len(E)):
            e = E[i]
            
            if (UF.same(e[0], e[1])) == False:
                UF.unite(e[0], e[1])
                res_E.append(e)

        return res_E

    def node(self):
        UF = UnionFind(len(V)) 
        res_V = []
        for i in range(len(E)):
            e = E[i]
            
            if (UF.same(e[0], e[1])) == False:
                UF.unite(e[0], e[1])
                res_V.append(e[0])
                res_V.append(e[1])

        return list(set(res_V))
        
A, B = map(int, input().split())
E = [list(map(int, input().split())) for _ in range(B)]

V = [i for i in range(A)]

kl = kruskal(V, E)

print(kl.weight())

Solution (Python):
import heapq


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

edges = []
for i in range(m):
    s, t, w = map(int, input().split())
    heapq.heappush(edges, (w, s, t))

cost = 0
roots = [i for i in range(n)]
clusters = {i: {i} for i in range(n)}

while len(edges) > 0:
    w, s, t = heapq.heappop(edges)

    if roots[s] != roots[t]:
        cluster = clusters.pop(roots[t])
        for elem in cluster:
            roots[elem] = roots[s]
        clusters[roots[s]] |= cluster
        cost += w

print(cost)

Solution (Python):
par , rank = [],[] 

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

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

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

edge = []

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

edge.sort()
mincost = 0

for i in range(v): 
    par.append(i)
    rank.append(0)

for ee in edge:
    w,s,t = ee
    if (find(s) != find(t)) :
        unite(s,t)
        mincost += w

print(mincost)

Solution (Python):
num_v,num_e=input().split()

edges=[]
verticies=[]

for i in range(int(num_e)):
    v,u,w=input().split()
    e=(v,u,int(w))
    edges.append(e)


for v in range(int(num_v)):
    v=str(v)
    verticies.append(v)





graph={
    'verticies':verticies,
    'edges':edges
}


parent={}
g_len={}

def group(v):
    parent[v]=v
    g_len[v]=0

def my_parent(v):
    if parent[v]!=v:
        parent[v]=my_parent(parent[v])
    return parent[v]
    
    
def union(v, u): 
    g_v=my_parent(v)
    g_u=my_parent(u)
    if g_v != g_u:
        if g_len[g_v] >= g_len[g_u]:
            parent[g_u]=parent[g_v]
            g_len[g_v] +=1
        else:
            parent[g_v]=parent[g_u]
            g_len[g_u] +=1
            

def kruskal(graph):
    g_list=[]
    sum_w=0
    
    for v in graph['verticies']:
        group(v)
        
    edges=graph['edges']
    edges.sort(key=lambda edges:edges[2])
    
    for edge in edges:
        v, u, weight =edge
        
        if my_parent(v) != my_parent(u):
            union(v,u)
            g_list.append(edge)
            sum_w=sum_w + weight
            
    return sum_w
    

print(kruskal(graph))

Solution (Python):
class DisjointSetElement():
    def __init__(self, x):
        self.parent = x
        self.rank = 0


class DisjointSet():
    def __init__(self, n):
        self.elems = [DisjointSetElement(n) for n in range(n)]

    def _find_set(self, x):
        if x != self.elems[x].parent:
            self.elems[x].parent = self._find_set(self.elems[x].parent)
        return self.elems[x].parent

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

    def _link(self, x, y):
        if self.elems[x].rank > self.elems[y].rank:
            self.elems[y].parent = x
        else:
            self.elems[x].parent = y
            if self.elems[x].rank == self.elems[y].rank:
                self.elems[y].rank += 1

    def unite(self, x, y):
        self._link(self._find_set(x), self._find_set(y))

    def is_alone(self, x):
        return x == self.elems[x].parent


def read_inputs():
    nv, ne = [int(x) for x in input().split()]

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

    return nv, E


def min_sp_tree(nv, E):
    K = DisjointSet(nv)
    total = 0
    n = 0

    i = iter(E)
    while n < nv - 1:
        w, s, t = next(i)
        if not K.same(s, t):
            K.unite(s, t)
            total += w
            n += 1

    return total


def main():
    nv, E = read_inputs()
    E.sort()
    print(min_sp_tree(nv, E))


if __name__ == '__main__':
    main()

Solution (Python):
import sys
fin = sys.stdin.readline
from heapq import heapify, heappop, heappush


class UnionFind(object):
    def __init__(self, N):
        self.__root = list(range(N))
    

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

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


    def unite(self, x, y):
        x = self.root(x)
        y = self.root(y)
        if (x == y):
            return
        self.__root[y] = x
        return





def prim(adj, w):
    num_vertices = len(adj)
    
    min_cost = [float('inf')] * num_vertices
    min_cost[0] = 0
    used = [False] * num_vertices
    priority_queue = [(0, 0)]
    total_cost = 0

    while priority_queue:
        cost, vertex = heappop(priority_queue)
        if cost > min_cost[vertex] or used[vertex]:
            continue
        used[vertex] = True
        total_cost += cost

        for neighbor in adj[vertex]:
            cost_v_to_n = w[vertex][neighbor]
            if min_cost[neighbor] > cost_v_to_n:
                min_cost[neighbor] = cost_v_to_n
                heappush(priority_queue, (cost_v_to_n, neighbor))

    return total_cost





def kruskal(edges_with_cost, num_vertices):
    
    edges_with_cost.sort(key=lambda x: x[-1])
    uf = UnionFind(num_vertices)
    total_cost = 0
    for source, target, cost in edges_with_cost:
        if not uf.same(source, target):
            uf.unite(source, target)
            total_cost += cost
    
    return total_cost



V, E = [int(elem) for elem in fin().split()]
edges_with_cost = []
for _ in range(E):
    s, t, w = [int(elem) for elem in fin().split()]
    edges_with_cost.append((s, t, w))

print(kruskal(edges_with_cost, V))

Solution (Python):

def input(f):
    global v, e, s, t, w
    
    v, e = map(int, f.readline().split())
    s = []
    t = []
    w = []
    for _ in range(e):
        s_, t_, w_ = map(int, f.readline().split())
        s.append(s_)
        t.append(t_)
        w.append(w_)

import os

if os.environ.get('ZEPPELIN_HOME'):
    import networkx as nx
    import matplotlib.pyplot as plt
    
    def visualize():
        G = nx.MultiDiGraph()
        for i in range(v):
            G.add_node(i, node_color='b')
        for i in range(e):
            G.add_edge(s[i], t[i], t=w[i])

        plt.figure()
        plt.style.use('seaborn')
        plt.axis("off")
        pos = nx.spring_layout(G)
        nodes = nx.draw_networkx_nodes(G, pos, node_color='w', linewidths=2)
        nodes.set_edgecolor('black')
        nx.draw_networkx_labels(G, pos)
        nx.draw_networkx_edges(G, pos)

        edge_labels = dict([((a, b), c['t']) for a, b, c in G.edges(data=True)])
        nx.draw_networkx_edge_labels(G, pos, edge_labels=edge_labels, label_pos=0.25, font_size=16)

        plt.show()

if os.environ.get('ZEPPELIN_HOME'):
    with open('/tmp/input1') as f:
        print('Example 
        input(f)
        visualize()

if os.environ.get('ZEPPELIN_HOME'):
    with open('/tmp/input2') as f:
        print('Example 
        input(f)
        visualize()

import sys
import heapq


class UnionFind:
    def __init__(self, v):
        self.parent = [-1] * v
    
    def find(self, x):
        if self.parent[x] == -1:
            return x
        else:
            self.parent[x] = self.find(self.parent[x])
            return self.parent[x]
    
    def merge(self, x, y):
        px = self.find(x)
        py = self.find(y)
        if px != py:
            self.parent[py] = px
    
    def is_same(self, x, y):
        return self.find(x) == self.find(y)


def init():
    global inf
    inf = sys.maxsize


def solve():
    q = []
    for i in range(e):
        heapq.heappush(q, (w[i], i))
    
    res = 0
    uf = UnionFind(v)
    while len(q) > 0:
        wi, i = heapq.heappop(q)
        if not uf.is_same(s[i], t[i]):
            uf.merge(s[i], t[i])
            res += wi
    
    print(res)

if os.environ.get('ZEPPELIN_HOME'):
    os.environ['INPUT'] = '/tmp/input1'

with open(os.environ.get('INPUT') or '/dev/stdin') as f:
    input(f)
    init()
    solve()

if os.environ.get('ZEPPELIN_HOME'):
    os.environ['INPUT'] = '/tmp/input2'

    with open(os.environ.get('INPUT') or '/dev/stdin') as f:
        input(f)
        init()
        solve()

if os.environ.get('ZEPPELIN_HOME'):
    os.environ['INPUT'] = '/tmp/input3'

    with open(os.environ.get('INPUT') or '/dev/stdin') as f:
        input(f)
        init()
        solve()

if os.environ.get('ZEPPELIN_HOME'):
    os.environ['INPUT'] = '/tmp/input3'

    with open(os.environ.get('INPUT') or '/dev/stdin') as f:
        input(f)
        init()
        solve()

Solution (Python):
import heapq
from collections import deque
from enum import Enum
import sys
import math
from _heapq import heappush, heappop

BIG_NUM = 2000000000
MOD = 1000000007
EPS = 0.000000001


class UnionFind:
    def __init__(self,arg_V):
        self.V = arg_V
        self.boss = [None]*arg_V
        self.height = [None]*arg_V

    def init(self):
        for i in range(self.V):
            self.boss[i] = i
            self.height[i] = 0

    def get_boss(self,index):
        if index == self.boss[index]:
            return index
        else:
            self.boss[index] = self.get_boss(self.boss[index])
            return self.boss[index]


    def is_same_group(self,a,b):
        return self.get_boss(a) == self.get_boss(b)

    def unite(self,x,y):
        boss_x = self.get_boss(x)
        boss_y = self.get_boss(y)

        if boss_x == boss_y:
            return

        if self.height[x] > self.height[y]:

            self.boss[boss_y] = boss_x

        elif self.height[x] < self.height[y]:

            self.boss[boss_x] = boss_y

        else:
            self.boss[boss_y] = boss_x
            self.height[x] += 1

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

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



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

UF = UnionFind(V)
UF.init()

table = []

for loop in range(E):
    tmp_from,tmp_to,tmp_cost = map(int,input().split())
    edge = Edge(tmp_from,tmp_to,tmp_cost)
    table.append(edge)

table.sort()

ans = 0

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


print("%d"%(ans))

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

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

def unite(x, y):
  x = root(x)
  y = root(y)
  par[x] = y

v, e = map(int,input().split())
adj = [list(map(int, input().split())) for i in range(e)]
adj.sort(key = lambda x:x[2])
par = [i for i in range(v)]
sum = 0

for i, j, k in adj:
  if not same(i, j):
    sum += k
    unite(i, j)
print(sum)

Solution (Python):
class DisjointSet:
    def __init__(self, size):
        self.rank = [0] * size
        self.p = list(range(size))

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

    def same(self, x, y):
        return 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 unite(self, x, y):
        self.link(self.findSet(x), self.findSet(y))


class Edge:
    def __init__(self, source=0, target=0, cost=0):
        self.source = source
        self.target = target
        self.cost = cost

def kruskal(n, edges):
    totalCost = 0
    edges.sort(key=lambda e: e.cost)
    dset = DisjointSet(n)

    for e in edges:
        if not dset.same(e.source, e.target):
            totalCost += e.cost
            dset.unite(e.source, e.target)

    return totalCost


if __name__ == '__main__':
    n, m = [int(v) for v in input().split()]
    edges = []
    for i in range(m):
        s, t, w = [int(v) for v in input().split()]
        edges.append(Edge(s, t, w))

    print(kruskal(n, edges))

Solution (Python):


from collections import namedtuple
from heapq import heappop, heappush


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

    def union(self, p, q):
        rp = self.root(p)
        rq = self.root(q)
        if self.sizes[rp] > self.sizes[rq]:
            self.nodes[rq] = rp
            self.sizes[rp] += self.sizes[rq]
        else:
            self.nodes[rp] = rq
            self.sizes[rq] += self.sizes[rp]

    def connected(self, p, q):
        return self.root(p) == self.root(q)

    def root(self, p):
        while p != self.nodes[p]:
            self.nodes[p] = self.nodes[self.nodes[p]]
            p = self.nodes[p]

        return p


WEIGHT_MAX = 10 ** 10
WeightedEdge = namedtuple('WeightedEdge', ('src', 'dest', 'weight'))


class Digraph:
    def __init__(self, v):
        self.v = v
        self._edges = [[] for _ in range(v)]

    def add(self, edge):
        self._edges[edge.src].append(edge)

    def adj(self, v):
        return self._edges[v]

    def edges(self):
        for es in self._edges:
            for e in es:
                yield e


def mst_kruskal(graph):
    edges = []
    for e in graph.edges():
        heappush(edges, (e.weight, e))

    uf = UnionFind(graph.v)
    conn = 0
    weight = 0
    while conn < graph.v-1:
        w, e = heappop(edges)
        if not uf.connected(e.src, e.dest):
            uf.union(e.src, e.dest)
            conn += 1
            weight += w

    return weight


def run():
    v, e = [int(i) for i in input().split()]
    graph = Digraph(v)

    for _ in range(e):
        s, t, w = [int(i) for i in input().split()]
        graph.add(WeightedEdge(s, t, w))

    print(mst_kruskal(graph))


if __name__ == '__main__':
    run()

Solution (Python):
import heapq

class Adjlist_weighted():

    def __init__(self, nodes, edges = None):
        self.nodes = nodes
        lis = [{} for i in range(nodes)]
        if edges is not None:
            for edge in edges:
                lis[edge[0]][edge[1]] = edge[2]
        self.edges = lis

    def add_edge(self, edge):
        self.edges[edge[0]][edge[1]] = edge[2]
        self.edges[edge[1]][edge[0]] = edge[2]
        return self

    def next_edges(self,x):
        return self.edges[x]

class Min_span_tree():

    def __init__(self, graph):
        min_span_tree = Adjlist_weighted(graph.nodes)
        searched_nodes = [False]*graph.nodes
        start = 0
        heap = [(0, start, start)]
        total_length = 0
        while heap:
            (cost, now, prev) = heapq.heappop(heap)
            if not searched_nodes[now]:
                searched_nodes[now] = True
                if (now, prev) != (start, start):
                    min_span_tree.add_edge((prev, now, cost))
                cand = graph.next_edges(now)
                total_length += cost
                for next in cand:
                    if not searched_nodes[next]:
                        heapq.heappush(heap, (cand[next], next, now))
        self.min_span_tree = min_span_tree
        self.total_length = total_length
    

(V, E) = tuple(map(int, input().split(" ")))
graph = Adjlist_weighted(V)
for _ in range(E):
    graph.add_edge(tuple(map(int, input().split(" "))))
mst = Min_span_tree(graph)
print(mst.total_length)

Solution (Python):
from collections import defaultdict 
import sys
import heapq
sys.setrecursionlimit(10**8)

def Find(x):	
	global table

	if table[x] == x:
		return x
	else:
		table[x] = Find(table[x])	
		return table[x]

def Union(x,y):	
	x = Find(x)	
	y = Find(y)
	
	if x == y:
		return
	
	if rank[x] > rank[y]:
		table[y] = x
	else:
		table[x] = y
		if rank[x] == rank[y]:
			rank[y] += 1

def Check(x,y):
	if Find(x) == Find(y):
		return True
	else:
		return False




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


table = [i for i in range(N)]	
rank  = [1 for i in range(N)]	


q = []
heapq.heapify(q)


rout = defaultdict(set)
for i in range(E):
	a,b,w = list(map(int,input().split()))
	rout[a].add(b)
	rout[b].add(a)
	heapq.heappush(q,[w,a,b])

weight = 0
	
while q:
	w,a,b = heapq.heappop(q)
	
	if not Check(a,b):
		weight += w
		Union(a,b)
		
print(weight)