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|
s0 t0 w0
s1 t1 w1
:
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.

si and ti represent source and target verticess of i-th edge (undirected) and wi 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 ≤ wi ≤ 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



Sample input:
4 6
0 1 2
1 2 1
2 3 1
3 0 1
0 2 3
1 3 5


Sample output:
3

Submission status: Accepted

Solution code:
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:
            # root abbreviation
            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


# assuming that the vertices are 0, 1, ..., N - 1
# time complexity: O(ElgE)
# space complexity: O(E)
def prim(adj, w):
    num_vertices = len(adj)
    # initialize
    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


# input should be [(s1, t1, cost1), (s2, t2, cost2), ...]
# time complexity: O(ElgV)
# space complexity: O(V)
def kruskal(edges_with_cost, num_vertices):
    # num_edges = len(edges_with_cost)
    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))

Submission status: Accepted

Solution code:

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 #1')
        input(f)
        visualize()

if os.environ.get('ZEPPELIN_HOME'):
    with open('/tmp/input2') as f:
        print('Example #2')
        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()

Submission status: Accepted

Solution code:
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))

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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))

Submission status: Accepted

Solution code:
# GRL_2_A: Minimum Spanning Tree

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

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

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

def Find(x):	#xの根を返す
	global table

	if table[x] == x:
		return x
	else:
		table[x] = Find(table[x])	#親の更新(根を直接親にして参照距離を短く)
		return table[x]

def Union(x,y):	#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:辺数 
N,E = map(int,input().split())

#Union-Find
table = [i for i in range(N)]	#木の親 table[x] == x なら根	
rank  = [1 for i in range(N)]	#木の長さ

# 優先度付きキューの作成
q = []
heapq.heapify(q)

#rout辞書
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)

Submission status: Runtime Error

Solution code:
import sys
from union_find import UnionFind
from operator import attrgetter

class Kruskal:

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

        def __lt__(self, another):
            return self.cost < another.cost

    def __init__(self, node_size):
        self._node = node_size
        self._edge_list = []

    def add_edge(self, u, v, cost):
        self._edge_list.append(self.Edge(u, v, cost))

    def solve(self):
        uf = UnionFind(self._node)
        res = 0
        edge_count = 0
        sorted_edge_list = sorted(self._edge_list)
        for e in sorted_edge_list:
            if not uf.same(e.u, e.v):
                uf.unite(e.u, e.v)
                res += e.cost
                edge_count += 1
                if edge_count == self._node-1:
                    break
        return res

if __name__ == '__main__':
    n, m = map(int, sys.stdin.readline().split())
    kr = Kruskal(n)
    for _ in range(m):
        s, t, w = map(int, sys.stdin.readline().split())
        kr.add_edge(s, t, w)
    print(kr.solve())

Submission status: Runtime Error

Solution code:
n = int(input())
m = [[-1 for i in range (n)] for j in range(n)]
d = [0]+ [2000]* (n-1)
isVisited = [False] * n


for i in range(n):
  nums = list(map(int, input().split()))
  for j in range(n):
    m[i][j] = nums[j]


# def prim_mst(n):

def prim_mst(n):
  while True:
    mincost = 2000
    for i in range(n):
      if (not isVisited[i]) and (d[i] < mincost):
        mincost = d[i]
        u = i

    isVisited[u] = True

    if mincost == 2000:
      break

    for v in range(n):
      if (not isVisited[v]) and (m[u][v] != -1):
        if m[u][v] < d[v]:
          d[v] = m[u][v]
  print(d)

prim_mst(n)

Submission status: Runtime Error

Solution code:
n = int(input())
m = [[-1 for i in range(n)] for j in range(n)] #お隣さんへのコストを保存（この中から最小を探す）

v = set()
v.add(0)

for i in range(n): #隣接の辺のコストを入力
  nums = list(map(int, input().split()))
  for j in range(n):
    m[i][j] = nums[j]


def prim_mst(n):
  isVisited = [False] * n
  d = [0] + [2001] * (n-1)      #TとV-Tのを繋ぐ最小辺の重みを格納する

  while  True:
    mincost = 2001
    for i in range(n):
      if not (isVisited[i]) and d[i] < mincost:
        mincost = d[i]
        u = i
    isVisited[u] = True


    if mincost == 2001:        #mincostが2001になったら繰り返し作業終了
      break

    for v in range (n):
      if (not isVisited[v]) and (m[u][v] != -1):
        if m[u][v] < d[v]:
          d[v] = m[u][v]
  print(sum(d))

prim_mst(n)

Submission status: Runtime Error

Solution code:
from heapq import heappush, heappop

line = input()
v, e = list(map(int, line.split()))
edge = {}
for _ in range(0, e):
    line = input()
    s, t, w = list(map(int, line.split()))
    if s not in edge:
        edge[s]  = [[t, w]]
    else:
        edge[s] += [[t, w]]
    if t not in edge:
        edge[t]  = [[s, w]]
    else:
        edge[t] += [[s, w]]

def solve(v, edge):
    q = []
    vtx = set([i for i in range(0, v)])
    for t, w in edge[0]:
        heappush(q, (w, 0, t))
    vn = set([0])
    en = []
    cost = 0
    while len(vn) < v:
        w = s = t = 0
        qq = []
        while q:
            w, s, t = heappop(q)
            if s in vn and t not in vn:
                s, t = t, s
                break
            if s not in vn and t in vn:
                break
        vn.add(s)
        en += [(s, t)]
        cost += w
        for t, w in edge[s]:
            heappush(q, (w, s, t))
    return cost
        
print(solve(v, edge))

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-

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

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

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

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

def union(x, y):
  a = find(x)
  b = find(y)
  parent[a] = b
  

sum_weight = 0

while weight:
  a, b, c = weight[0]
  if find(a) != find(b):
    union(a, b)
    sum_weight += c
  weight.pop(index=0)
  
print(sum_weight)

Submission status: Runtime Error

Solution code:
import heapq

nv, ne = map(int, input().split())

edges = [set() for _ in range(nv)]
while ne:
    s, t, w = map(int, input().split())
    edges[s].add((w, t))
    edges[t].add((w, s))
    ne -= 1

cost = 0
queue = list(edges[0])
heapq.heapify(queue)
visited = [False] * nv
visited[0] = True

while True:
    edge_cost, t = heapq.heappop(queue)
    if visited[t]:
        continue
    visited[t] = True
    cost += edge_cost
    if all(visited):
        break
    for e in edges[t]:
        if not visited[e[1]]:
            heapq.heappush(queue, e)

print(cost)

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
# -*- coding: utf-8 -*-

import collections
import heapq


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


# Prim?????§??????0?????????????°???¨?????¨????±???????
def compute_mst_prim(max_v, adj_list):
    # pred[u]?????????u???????????¨???????????????????????¨???
    pred = collections.defaultdict(lambda: NO_VERTEX)
    # u??¨pred[u]????????¶???????????????key[u]?????\???
    key = collections.defaultdict(lambda: INF)
    key[0] = 0
    # ??????????????????????????????????????\?????¨????????¨??????
    pq = []
    for v in range(max_v):
        heapq.heappush(pq, (key[v], v))
    while pq:
        _, u = heapq.heappop(pq)
        for v, v_cost in adj_list[u]:
            if v in (item[1] for item in pq):
                weight = v_cost
                if weight < key[v]:
                    pred[v] = u
                    key[v] = weight
                    heapq.heappush(pq, (weight, v))
    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()

Submission status: Runtime Error

Solution code:
from collections import defaultdict
import heapq

vertices,edges = map(int,input().split(" "))
link = defaultdict(dict)
weight = defaultdict(dict)

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 = set()
now_weight = 0

while len(went) < vertices:
    now_weight,here = heapq.heappop(queue)
    #print(now_weight,here)
    can_go = link[here] - went
    min_weight,next_t = float("inf"),-1
    for c in can_go:
        if min_weight > now_weight + weight[here][c]:
            min_weight = now_weight + weight[here][c]
            next_t = c
        #heapq.heappush(queue,[now_weight + weight[here][c],c])
    heapq.heappush(queue,[min_weight,next_t])
    #print(queue)
    went = went | {here}
print(now_weight)

Submission status: Runtime Error

Solution code:
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 = set()
now_weight = 0
way[0] = 0

while len(went) < vertices:
    here_weight,here = heapq.heappop(queue)
    #print(now_weight,here)
    now_weight += here_weight
    can_go = link.get(here,set()) - went
    min_weight,next_t = float("inf"),-1
    for c in can_go:
        #heapq.heappush(queue,[now_weight + weight[here][c],c])
        if c not in went and way[c] > [weight[here][c]:
            heapq.heappush(queue,[weight[here][c],c])
            way[c] = [weight[here][c]
    #print(queue)
    went = went | {here}
print(now_weight)

Submission status: Runtime Error

Solution code:
from collections import defaultdict
import heapq
def aaa()
    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 len(went) < vertices:
        here_weight,here = heapq.heappop(queue)
        if here in went:
            continue
        #print(now_weight,here)
        went[here] = 1
        now_weight += here_weight
        can_go = link.get(here,set()) - went
        min_weight,next_t = float("inf"),-1
        for c in can_go:
            #heapq.heappush(queue,[now_weight + weight[here][c],c])
            if c not in went and way[c] > weight[here][c]:
                heapq.heappush(queue,[weight[here][c],c])
                way[c] = weight[here][c]
        #print(queue)
    print(now_weight)

Submission status: Runtime Error

Solution code:

class Node:
    def __init__(self):
        pass

class Edge:
    def __init__(self,edge,cost=1):
        self.node_from=edge[0]
        self.node_to=edge[1]
        self.cost=cost

    def add_node(self,node):
        self.nodes.append(node)

class myGraph:

    def __init__(self):
        self.adj={}
        self.nodes={}

    def add_edge(self,edge,cost):
        if len(edge)==1:
            edge=list(edge)

        u,v=edge[0],edge[1]

        if u not in self.nodes:
            self.adj[u] = {}
            self.nodes[u] = {}

        if v not in self.nodes:
            self.adj[v] = {}
            self.nodes[v] = {}

        # add the edge
        self.adj[u][v] = cost
        self.adj[v][u] = cost

    def add_directed_edge(self,edge,cost):
        if len(edge)==1:
            edge=list(edge)


        u,v=edge[0],edge[1]

        if u not in self.nodes:
            self.adj[u] = {}
            self.nodes[u] = {}

        if v not in self.nodes:
            self.adj[v] = {}
            self.nodes[v] = {}

        self.adj[u][v] = cost

    def get_edges_from(self,node):
        return [(self.adj[node][nn],node,nn) for nn in self.adj[node]]


    def makeEdgeobj(self):
        edges=[]
        for sn in self.nodes:
            for e in self.get_edges_from(sn):
                edges.append(Edge([e[1],e[2]],e[0]))

        return edges

    def _add(self,edges,add_edges):
        for e in add_edges:
            hq.heappush(edges,e)
        return edges

    def bermn_ford(self,start,init=0):

        nodes=self.nodes
        dists={}
        for n in nodes:
            dists[n]=float("inf")

        dists[start]=init
        edges=self.makeEdgeobj()

        for i in range(len(nodes)):
            update=False
            for k in range(len(edges)):
                e=edges[k]
                if  dists[e.node_from]!=float("inf") and dists[e.node_to]>dists[e.node_from]+e.cost:
                    dists[e.node_to]=dists[e.node_from]+e.cost
                    update=True

            if i==len(nodes)-1:
                return False

            if not update:
                break

        return dists


    def dijkstra(self,start, goal=None):
        import heapq
        '''
            get minimum cost
        '''

        N = len(self.adj)          # ??°????????????????????°
        #dist = [float('inf') for i in range(N)] # ?§????????????????????????§??????????????¢???????´???????
        dist = {k:float('inf') for k in self.nodes}
        #prev = [float('inf') for i in range(N)]

        dist[start] = 0
        visited = []

        koho=[]
        heapq.heappush(koho,(0,start))

        vtx=list(self.nodes)
        vtx.remove(start)

        while len(koho)!=0:
            d,mini=heapq.heappop(koho)
            if dist[mini]<d:
                continue


            for k in list(self.adj[mini]):
                cost=self.adj[mini][k]
                if cost != float('inf') and dist[k]>dist[mini]+cost:# and not(k in visited):
                    dist[k]=dist[mini]+cost
                    heapq.heappush(koho,(dist[k],k))
                    #prev[k]=mini

        return dist

    def prim(self):
        import heapq

        nodes=list(self.nodes.keys())
        N=len(nodes)

        X=[nodes[0]]
        unused=[]
        for u in self.adj[X[0]]:
            heapq.heappush(unused,(u,self.adj[X[0]][u]))

        total_cost=0
        while True:
            v,cost=heapq.heappop(unused)

            X.append(v)
            total_cost+=cost
            if len(X)==N:
                break

            for u in self.adj[v]:
                heapq.heappush(unused,(u,self.adj[v][u]))



        return total_cost




    def show(self):

        import networkx as nx
        import matplotlib.pyplot as plt
        G=nx.Graph()

        for e in self.edges:

            G.add_edge(e.node_from,e.node_to,weight=e.cost)
            #print(e.node_from,e.node_to,e.cost)

        pos=nx.spring_layout(G)
        #nx.draw_networkx_edges(G,pos=pos,edgelist=G.edges())
        edge_weight=dict([((u,v,),int(d['weight'])) for u,v,d in G.edges(data=True)])

        nx.draw_networkx_edge_labels(G,pos,edge_labels=edge_weight)
        #nx.draw_networkx_labels(G, pos)
        nx.draw_networkx_nodes(G,pos)
        nx.draw_networkx_edges(G,pos)
        nx.draw_networkx_labels(G,pos)
        #plt.axis('off')
        #nx.draw(G,with_labels=True)
        plt.show()



def spaceinput():
    s=input()
    if len(s)==0:
        return False

    return list(map(int,s.split(" ")))

if __name__=="__main__":
    a=spaceinput()
    g=myGraph()


    for i in range(9):
        ss=spaceinput()
        if not ss:
            break

        g.add_edge((ss[0],ss[1]),ss[2])

    print(g.prim())

    '''
    d=g.dijkstra(1)
    '''



    '''
    mint=10*9
    for k in range(1,n+1):
        dd=g.dijkstra(k)
        v=max(dd.values())
        if mint>v:
            mint=v


    print(mint)
    '''