Problem:
Minimum Spanning Tree For a given weighted graph $G = (V, E)$, find the minimum spanning tree (MST) of $G$ and print total weight of edges belong to the MST. Input In the first line, an integer $n$ denoting the number of vertices in $G$ is given. In the following $n$ lines, a $n \times n$ adjacency matrix $A$ which represents $G$ is given.
$a_{ij}$ denotes the weight of edge connecting vertex $i$ and vertex $j$. If there is no edge between $i$ and $j$, $a_{ij}$ is given by -1. Output Print the total weight of the minimum spanning tree of $G$. Constraints  $1 \leq n \leq 100$  $0 \leq a_{ij} \leq 2,000$ (if $a_{ij} \neq -1$)  $a_{ij} = a_{ji}$  $G$ is a connected graph  Sample Input 1 5
 -1 2 3 1 -1
 2 -1 -1 4 -1
 3 -1 -1 1 1
 1 4 1 -1 3
 -1 -1 1 3 -1 Sample Output 1 5 Reference Introduction to Algorithms, Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. The MIT Press.

Solution (Python):

from collections import deque


class Graph:
    def __init__(self, n, adj_matrix, default_value=float('inf')):
        self.n = n
        self.adj_matrix = adj_matrix
        self.default_value = default_value

    def show(self):
        for _ in self.adj_matrix:
            print(*_)

    def set_mst(self, start=0):  
        self.mst = []
        T = [start]

        for _ in range(self.n - 1):
            edges = [(cost, u, v) for u in T
                     for v, cost in enumerate(self.adj_matrix[u])
                     if cost != self.default_value and v not in T]

            min_cost, *min_edge = min(edges)
            self.mst.append(tuple(min_edge))
            T.append(min_edge[1])

    def show_mst(self):
        self.set_mst()
        print(sum([self.adj_matrix[u][v] for u, v in self.mst]))

    def dfs(self):
        self.states = [2] * self.n
        self.d = [None] * self.n
        self.f = [None] * self.n
        self.time = 0

        for u in range(self.n):
            if self.states[u] == 2:
                self.dfs_visit(u)

    def dfs_visit(self, u):
        self.states[u] = 1
        self.time += 1
        self.d[u] = self.time

        for v, edge in [(v, edge) for v, edge in enumerate(self.adj_matrix[u])
                        if edge]:
            if self.states[v] == 2:
                self.dfs_visit(v)

        self.states[u] = 0
        self.time += 1
        self.f[u] = self.time

    def show_dfs(self, start=0):
        self.dfs()
        for i, (d, f) in enumerate(zip(self.d, self.f)):
            print(i + 1, d, f)

    def bfs(self, start):
        self.states = [0] * self.n
        self.dists = [float('inf')] * self.n

        queue = deque([start])
        self.dists[start] = 0
        while queue:
            u = queue.popleft()
            edges = self.adj_matrix[u]

            for v, edge in [(v, edge) for v, edge in enumerate(edges) if edge]:
                if self.states[v]:
                    continue

                if self.dists[v] > self.dists[u] + 1:
                    self.dists[v] = self.dists[u] + 1
                queue.append(v)

                self.states[v] = 1

        self.dists = [
            -1 if dist == float('inf') else dist for dist in self.dists
        ]

    def show_bfs(self, start=0):
        self.bfs(start=start)
        for i, dist in enumerate(self.dists):
            print(i + 1, dist)


if __name__ == '__main__':
    n = int(input())
    adj_matrix = [[
        int(cost) if int(cost) != -1 else float('inf')
        for cost in input().split()
    ] for i in range(n)]

    g = Graph(n, adj_matrix)
    g.show_mst()

Solution (Python):

def prim(edges, *, start=0, adj_matrix=False, default_value=float('inf')):
    '''
    Returns the Minimum Spanning Tree(MST) of a given graph

    
    edges = [[0, 2, 5, 4, inf, inf],           
             [2, 0, inf, 3, 6, inf],           
             [5, inf, 0, 2, inf, 6],           
             [4, 3, 2, 0, 2, inf],             
             [inf, 6, inf, 2, 0, 4],           
             [inf, inf, 6, inf, 4, 0]]         

    
    edges = [[(1, 2), (2, 5), (3, 4)],         
             [(0, 2), (3, 3), (4, 6)],         
             [(0, 5), (3, 2), (5, 6)],         
             [(0, 4), (1, 3), (2, 2), (4, 2)], 
             [(1, 6), (3, 2), (5, 4)],         
             [(2, 6), (4, 4)]]                 
    '''

    n = len(edges)
    mst = []
    cost = 0
    T = [start]

    while True:
        tmp_edges = [(cost, (u, v)) for u in T for v, cost in enumerate(edges[u]) if cost != default_value and v not in T] if adj_matrix else\
                    [(cost, (u, v)) for u in T for v, cost in edges[u] if v not in T]

        if tmp_edges:
            min_cost, min_edge = min(tmp_edges)
            mst.append(min_edge)
            cost += min_cost
            T.append(min_edge[1])

        else:
            if len(mst) != n - 1:
                raise NoSpanningError(
                    'There is no spanning tree in this graph (search started from node{})'.
                    format(start))

            else:
                return mst, cost


class NoSpanningError(Exception):
    pass


if __name__ == '__main__':
    '''
    an example of using this function
    AIZU ONLINE JUDGE - ALDS_1_12_A
    '''

    n = int(input())
    edges = [[int(cost) if int(cost) != -1 else float('inf') for cost in input().split()] for i in range(n)]

    print(prim(edges, adj_matrix=True)[1])

Solution (Python):

def prim(edges, *, start=0, adj_matrix=False, default_value=float('inf')):
    '''
    Returns the Minimum Spanning Tree(MST) of a given graph

    
    edges = [[(1, 2), (2, 5), (3, 4)],         
             [(0, 2), (3, 3), (4, 6)],         
             [(0, 5), (3, 2), (5, 6)],         
             [(0, 4), (1, 3), (2, 2), (4, 2)], 
             [(1, 6), (3, 2), (5, 4)],         
             [(2, 6), (4, 4)]]                 

    
    edges = [[0, 2, 5, 4, inf, inf],           
             [2, 0, inf, 3, 6, inf],           
             [5, inf, 0, 2, inf, 6],           
             [4, 3, 2, 0, 2, inf],             
             [inf, 6, inf, 2, 0, 4],           
             [inf, inf, 6, inf, 4, 0]]         
    '''

    n = len(edges)
    mst = []
    cost = 0
    T = [start]

    while True:
        tmp_edges = [(cost, (u, v)) for u in T for v, cost in enumerate(edges[u]) if cost != default_value and v not in T] if adj_matrix else\
                    [(cost, (u, v)) for u in T for v, cost in edges[u] if v not in T]

        if tmp_edges:
            min_cost, min_edge = min(tmp_edges)
            mst.append(min_edge)
            cost += min_cost
            T.append(min_edge[1])

        else:
            if len(mst) != n - 1:
                raise NoSpanningError(
                    'There is no spanning tree in this graph (search started from node{})'.
                    format(start))

            else:
                return mst, cost


class NoSpanningError(Exception):
    pass


if __name__ == '__main__':
    '''
    an example of using this function
    AIZU ONLINE JUDGE - ALDS_1_12_A
    '''

    n = int(input())
    edges = [[int(cost) if int(cost) != -1 else float('inf') for cost in input().split()] for i in range(n)]

    print(prim(edges, adj_matrix=True)[1])

Solution (Python):

def prim(edges, *, start=0, adj_matrix=False, default_value=float('inf')):
    '''
    Returns the Minimum Spanning Tree(MST) of a given graph

    
    edges = [[(1, 2), (2, 5), (3, 4)],         
             [(0, 2), (3, 3), (4, 6)],         
             [(0, 5), (3, 2), (5, 6)],         
             [(0, 4), (1, 3), (2, 2), (4, 2)], 
             [(1, 6), (3, 2), (5, 4)],         
             [(2, 6), (4, 4)]]                 

    
    edges = [[0, 2, 5, 4, inf, inf],           
             [2, 0, inf, 3, 6, inf],           
             [5, inf, 0, 2, inf, 6],           
             [4, 3, 2, 0, 2, inf],             
             [inf, 6, inf, 2, 0, 4],           
             [inf, inf, 6, inf, 4, 0]]         
    '''

    n = len(edges)
    mst = []
    cost = 0
    T = [start]

    while True:
        tmp_edges = [(cost, (u, v)) for u in T for v, cost in enumerate(edges[u]) if cost != default_value and v not in T] if adj_matrix else\
                    [(cost, (u, v)) for u in T for v, cost in edges[u] if v not in T]

        if tmp_edges:
            min_cost, min_edge = min(tmp_edges)
            mst.append(min_edge)
            cost += min_cost
            T.append(min_edge[1])

        else:
            if len(mst) != n - 1:
                raise NoSpanningError(
                    'There is no spanning tree in this graph (search started from node{})'.
                    format(start))

            else:
                return mst, cost


class NoSpanningError(Exception):
    pass


if __name__ == '__main__':
    '''
    an example of using this function
    AIZU ONLINE JUDGE - ALDS_1_12_A
    '''

    n = int(input())
    edges = [[(j, int(cost)) for j, cost in enumerate(input().split()) if int(cost) != -1] for i in range(n)]

    print(prim(edges)[1])

Solution (Python):

from heapq import heappop, heappush


def prim(edges, *, start=0, adj_matrix=False, default_value=float('inf')):
    '''
    Returns the Minimum Spanning Tree(MST) of a given graph

    
    edges = [[(1, 2), (2, 5), (3, 4)],         
             [(0, 2), (3, 3), (4, 6)],         
             [(0, 5), (3, 2), (5, 6)],         
             [(0, 4), (1, 3), (2, 2), (4, 2)], 
             [(1, 6), (3, 2), (5, 4)],         
             [(2, 6), (4, 4)]]                 

    
    edges = [[0, 2, 5, 4, inf, inf],           
             [2, 0, inf, 3, 6, inf],           
             [5, inf, 0, 2, inf, 6],           
             [4, 3, 2, 0, 2, inf],             
             [inf, 6, inf, 2, 0, 4],           
             [inf, inf, 6, inf, 4, 0]]         
    '''

    n = len(edges)

    costs = [float('inf')] * n
    costs[start] = 0
    prevs = [-1] * n

    pq = [(0, start)]
    T = [True] * n

    while pq:
        tmp_cost, tmp_node = heappop(pq)
        T[tmp_node] = False

        nxt_edges = ((node, cost) for node, cost in enumerate(edges[tmp_node]) if cost != default_value and T[node]) if adj_matrix else\
                    ((node, cost) for node, cost in edges[tmp_node] if T[node])

        for nxt_node, nxt_cost in nxt_edges:
            if costs[nxt_node] > nxt_cost:
                costs[nxt_node] = nxt_cost
                prevs[nxt_node] = tmp_node
                heappush(pq, (nxt_cost, nxt_node))
                T[nxt_node] = True

    else:
        if len([prev for prev in prevs if prev != -1]) != n - 1:
            raise NoSpanningError(
                'There is no spanning tree in this graph (search started from node{})'.
                format(start))

        else:
            return prevs, costs


class NoSpanningError(Exception):
    pass


if __name__ == '__main__':
    '''
    an example of using this function
    AIZU ONLINE JUDGE - ALDS_1_12_A
    '''

    n = int(input())
    edges = [[(j, int(cost)) for j, cost in enumerate(input().split())
              if int(cost) != -1] for i in range(n)]

    prevs, costs = prim(edges)
    print(sum(costs))

Solution (Python):

from heapq import heappop, heappush


def prim(edges, *, start=0, adj_matrix=False, default_value=float('inf')):
    n = len(edges)

    costs = [float('inf')] * n
    costs[start] = 0
    prevs = [-1] * n

    pq = [(0, start)]
    T = [True] * n

    while pq:
        tmp_cost, tmp_node = heappop(pq)
        T[tmp_node] = False

        nxt_edges = ((node, cost) for node, cost in enumerate(edges[tmp_node]) if cost != default_value and T[node]) if adj_matrix else\
                    ((node, cost) for node, cost in edges[tmp_node] if T[node])

        for nxt_node, nxt_cost in nxt_edges:
            if costs[nxt_node] > nxt_cost:
                costs[nxt_node] = nxt_cost
                prevs[nxt_node] = tmp_node
                heappush(pq, (nxt_cost, nxt_node))
                T[nxt_node] = True

    else:
        if len([prev for prev in prevs if prev != -1]) != n - 1:
            raise NoSpanningError(
                'There is no spanning tree in this graph (search started from node{})'.
                format(start))
        else:
            return prevs, costs


class NoSpanningError(Exception):
    pass


if __name__ == '__main__':
    n = int(input())
    edges = [[(j, int(cost)) for j, cost in enumerate(input().split())
              if int(cost) != -1] for i in range(n)]

    prevs, costs = prim(edges)
    print(sum(costs))

Solution (Python):
import heapq

n = int(input())
A = [[int(i) for i in input().split()] for i in range(n)]
h = []
DP = {}
heapq.heappush(h,(0,0))
c = 0
while(len(DP)<n):
    tmp = heapq.heappop(h)
    if tmp[1] in DP:
        continue
    c += tmp[0]
    DP[tmp[1]] = 1
    for i,j in enumerate(A[tmp[1]]):
        if j > -1 and not i in DP:
            heapq.heappush(h,(j,i))
print(c)

Solution (Python):
import sys
def prim(n, m):
	d = [sys.maxsize]*n
	p = [-1]*n
	c = [False]*n
	d[0] = 0
	while True:
		minv = sys.maxsize
		u = -1
		for i in range(n):
			if minv > d[i] and c[i] == False:
				minv = d[i]
				u = i
		if u == -1:
			break
		c[u] = True
		for i in range(n):
			if m[u][i] != sys.maxsize:
				if m[u][i] < d[i] and c[i] == False:
						d[i] = m[u][i]
						p[i] = u
	sum = 0
	for i in range(n):
		if p[i] != -1:
			sum += m[i][p[i]]
	return sum

n = int(input())
m = [[0 for x in range(n)] for x in range(n)]
for i in range(n):
	a = list(map(int, input().split()))
	for j in range(n):
		if a[j] == -1:
			m[i][j] = sys.maxsize
		else:
			m[i][j] = a[j]
print(prim(n, m))

Solution (Python):


inf = 1000000000
n = int(input())
mtrx = []
for i in range(n):
    col2 = list(map(int,input().split()))
    col = []
    for num in col2:
        if num == -1:
            num = inf
        col.append(num)
    mtrx.append(col)

def prim():
    color = ["white" for i in range(n)]
    d = [inf for i in range(n)]
    p = [None for i in range(n)]
    p[0] = -1
    d[0] = 0

    while True:
        mincost = inf
        for i in range(n):
            if color[i] != "black" and d[i] < mincost:
                mincost = d[i]
                u = i

        if mincost == inf:
            break

        color[u] = "black"

        for v in range(n):
            if color[v] != "black" and mtrx[u][v] != inf:
                if mtrx[u][v] < d[v]:
                    d[v] = mtrx[u][v]
                    p[v] = u
                    color[v] = "gray"
    print(sum(d))

prim()

Solution (Python):

def judge_reachable(graph,start,end,flag):
    flag[start]=1
    for vertex in graph[start]:
        if(flag[vertex]==1):
            continue
        if (vertex==end):
            return 1
        if(judge_reachable(graph,vertex,end,flag)):
            return 1
    return 0



graph_n=int(input())


edge_dict={}



for i in range(graph_n):
    tmp_row=list(map(int,input().split()))
    for j in range(graph_n):
        if(tmp_row[j]!=-1):
            try:
                edge_dict[tmp_row[j]].append([i,j])
            except:
                edge_dict[tmp_row[j]]=[[i,j]]


sorted_edge=sorted(edge_dict.items())


graph=[[] for i in range(graph_n)]

edge_num=0
cost=0

for edges in sorted_edge:
    for edge in edges[1]:
        flag=[0]*graph_n
        if(judge_reachable(graph,edge[0],edge[1],flag)==0):
            graph[edge[0]].append(edge[1])
            graph[edge[1]].append(edge[0])
            edge_num+=1
            cost+=edges[0]
            if(edge_num ==graph_n - 1):
                break    
    if(edge_num ==graph_n -1):
        break

print(cost)

Solution (Python):
from sys import stdin

def read_matrix(n):
    A = []
    for _ in range(n):
        a = [ int(i) for i in stdin.readline().strip().split() ]
        A.append(a)
    return A

def prim(n, A):
    color = [ 'WHITE' for i in range(n) ]
    d = [ float('inf') for i in range(n) ]
    d[0] = 0
    p = [-1] * n

    while True:
        mincost = float('inf')
        for i in range(n):
            if color[i] != 'BLACK' and d[i] < mincost:
                mincost = d[i]
                u = i

        if mincost == float('inf'):
            break

        color[u] = 'BLACK'

        for v in range(n):
            if color[v] != 'BLACK' and A[u][v] != -1:
                if A[u][v] < d[v]:
                    d[v] = A[u][v]
                    p[v] = u
                    color[v] = 'GRAY'

    return sum(d)

n = int(input())
A = read_matrix(n)
print(prim(n, A))

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

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

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

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

Solution (Python):
n=int(input())
M=[list(map(int,input().split()))for _ in[0]*n]
d=[0]+[1e4]*n
b=[1]*n
a=0
while 1:
 u=-1
 for i in range(n):
  if b[i]and(u<0 or d[i]<d[u]):u=i
 if u<0:break
 b[u]=0
 a+=d[u]
 for v in range(n):
  t=M[u][v]
  if t+1 and d[v]>t:d[v]=t
print(a)

Solution (Python):
n=int(input())
m=[list(map(int,input().split()))for _ in[0]*n]

d=[0]+[10**9]*n
b=[1]*n
a=0
while 1:
  u=-1
  for i in range(n):
    if b[i] and (u<0 or d[i]<d[u]):
      u=i
  if u<0:
    break
  b[u]=0
  a+=d[u]
  for v in range(n):
    t=m[u][v]
    if t+1 and d[v]>t:
      d[v]=t
print(a)

Solution (Python):
n=int(input())

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

d=[0]+[10**9]*n
b=[1]*n
a=0
while 1:
  u=-1
  for i in range(n):
    if b[i] and (u<0 or d[i]<d[u]):
      u=i
  if u<0:
    break
  b[u]=0
  a+=d[u]
  for v in range(n):
    t=m[u][v]
    if t+1 and d[v]>t:
      d[v]=t
print(a)

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

d=[0]+[10**9]*n
visited=[0]*n
a=0
while 1:
  u=-1
  for i in range(n):
    if not visited[i] and (u<0 or d[i]<d[u]):
      u=i
  if u<0:
    break
  visited[u]=1
  a+=d[u]
  for v in range(n):
    t=m[u][v]
    if t+1 and d[v]>t:
      d[v]=t
print(a)

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

d=[0]+[10**9]*(n-1)
visited=[0]*n

while 1:
  u=-1
  for i in range(n):
    if not visited[i] and (u<0 or d[i]<d[u]):
      u = i
  if u < 0:
    break
  visited[u]=1
  for v in range(n):
    if not visited[v] and m[u][v]!=-1:
      if m[u][v]<d[v]:
        d[v]=m[u][v]

print(sum(d))

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

N = int(input())
edges = [[] for i in range(N)]
for v in range(N):
    for w, c in enumerate(map(int, input().split())):
        if c != -1:
            edges[v].append((w, c))

visited = [0]*N
que = [(c, w) for w, c in edges[0]]
visited[0] = 1
heapify(que)

d=[0]+[10**9]*(N-1)


ans = 0
while que:
    c, u = heappop(que)
    if visited[u]:
        continue
    visited[u] = 1
    d[u]=c
    for v, c in edges[u]:
        if visited[v]:
          continue
        heappush(que, (c, v))
print(sum(d))

Solution (Python):


import sys

sys.setrecursionlimit(10 ** 9)
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
INF=float('inf')


class UnionFind:
    def __init__(self, n):
        self.n = n
        
        
        self.par = [i for i in range(n+1)]
        
        self.rank = [0] * (n+1)
        
        self.size = [1] * (n+1)
        
        self.tree = [True] * (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 x == y:
            self.tree[x] = False
            return
        if not self.tree[x] or not self.tree[y]:
            self.tree[x] = self.tree[y] = False

        
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
            self.size[y] += self.size[x]
        else:
            self.par[y] = x
            self.size[x] += self.size[y]
            
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

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

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

    
    def is_tree(self, x):
        return self.tree[self.find(x)]

    
    def len(self):
        res = set()
        for i in range(self.n+1):
            res.add(self.find(i))
        
        return len(res) - 1

N=INT()
G=[[None] for i in range(N)]
for i in range(N):
    G[i]=LIST()


edges=[]
for i in range(N):
    for j in range(i+1, N):
        if G[i][j]!=-1:
            edges.append((G[i][j], i, j))


edges.sort()
uf=UnionFind(N)
ans=0
for cost, u, v in edges:
    if not uf.same(u, v):
        uf.union(u, v)
        ans+=cost
print(ans)

Solution (Python):


class UnionFind:
    def __init__(self,N):
        self.par = [i for i in range(N)]
        self.rank = [1]*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 Edge:
    def __init__(self, u, v, cost):
        self.u = u
        self.v = v
        self.cost = cost

def kruskal():
    es.sort(key=lambda x: x.cost)
    uf = UnionFind(V)
    res = 0
    for i in range(E):
        if not uf.same(es[i].u, es[i].v):
            uf.unite(es[i].u, es[i].v)
            res += es[i].cost
            
    return res

V = int(input().rstrip())
E = 0
es = []
for i in range(V):
    line = list(map(int, input().rstrip().split()))
    for j in range(V):
        if line[j] != -1:
            es.append(Edge(i,j,line[j]))
            E += 1

ans = kruskal()
print(ans)

Solution (Python):
INF = 99999999999999999999999999
n = int(input())
graph = [[-1] * (n+1) for _ in range(n+1)]
mst = [[-1] * (n+1) for _ in range(n+1)]
V = [ele for ele in range(1, n+1)]
T = []

for i in range(1, n + 1):
    tmp = [int(ele) for ele in input().split()]
    graph[i][1:] = tmp


def my_mst_solver():
    
    
    
    
    ans = 0
    edges = [[0]]
    for i in range(1, n + 1):
        tmp = []
        for to, w in enumerate(graph[i][1:], 1):
            if w != -1:
                tmp.append([w, to])
        tmp.sort()  
        edges.append(tmp)

    
    root = 1
    T.append(root)
    
    
    

    while set(T) != set(V):
        tmp = [INF, INF]
        for i in T:
            if edges[i] != [] and edges[i][0] < tmp:
                tmp = edges[i][0]
                idx = i
        else:
            
            ans += tmp[0]
            T.append(tmp[1])
            mst[idx][tmp[1]] = tmp[0]
            mst[tmp[1]][idx] = tmp[0]
            
            for k in range(1, n + 1):
                edges[k] = list(filter(lambda x: x[1] not in T, edges[k]))

    print(ans)


if __name__ == "__main__":
    my_mst_solver()

Solution (Python):
class Forest:
    def __init__(self, g, id):
        self.forest = set([id])
        self.graph = g
        self.next_wait = self.graph[id]
        self.wait = 0
    def add_tree(self, id):
        self.wait += self.next_wait[id]
        self.forest.update([id])
         
        self.marge_next_wait(id)
    def next_tree(self):
        min_id = min_wait = None
        for id, wait in self.next_wait.items():
            if id not in self.forest:
                if min_wait == None or min_wait > wait:
                    min_wait = wait
                    min_id = id
        return min_id
    def marge_next_wait(self, merge_id):
        for id, wait in self.graph[merge_id].items():
            if id not in self.next_wait or self.next_wait[id] > wait:
                self.next_wait[id] = wait
n = int(input())
g = [{e:i for e, i in enumerate(map(int, input().split())) if i != -1} for _ in range(n)]
forest = Forest(g,0)
for i in range(n - 1):
    id = forest.next_tree()
    forest.add_tree(id)
print(forest.wait)

Solution (Python):

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

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

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

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

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


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

def kruskal(es, V):
    es.sort(key=lambda x: x.cost)
    unionfind = UnionFind(V)
    res = 0
    for e in es:
        if unionfind.same(e.u, e.v):
            continue
        unionfind.union(e.u, e.v)
        res += e.cost
    return res

if __name__ == '__main__':
    n = int(raw_input())
    es = []
    for i in xrange(n):
        vs = map(int, raw_input().split())
        for j in xrange(i):
            if vs[j] != -1:
                es.append(Edge(i, j, vs[j]))

    print kruskal(es, n)

Solution (Python):
import sys

if __name__ == "__main__":
    
    
    
    
    
    
    
    lines = sys.stdin.readlines()
    matrix = [[int(x) for x in line.strip().split(" ")] for line in lines[1:] if line.strip() != ""]

    connections = set([0])  
    dimension = int(lines[0])
    cost = 0

    while len(connections) < dimension:
        minimum = sys.maxsize
        candidate = None

        for i in connections:
            for index, value in enumerate(matrix[i]):
                if value != -1 and value < minimum and index not in connections:
                    minimum = matrix[i][index]  
                    candidate = index

        connections.add(candidate)
        cost += minimum

    
    print(cost)

Solution (Python):
INFTY = 10000000000000000000000000000
n = int(raw_input())
A = {}
for i in range(n):
    A[i] = {}
    for j,c in enumerate(raw_input().strip().split(' ')):
        c = int(c)
        if c > -1: A[i][j] = c

d = {}
chosen = {}
for i in range(n):
    d[i] = INFTY
    chosen[i] = False
d[0] = 0

ans = 0
while True:
    mincost = INFTY
    u = -1
    for i in range(n):
        if (not chosen[i]) and mincost > d[i]:
            mincost = d[i]
            u = i
    if mincost == INFTY: break
    ans += mincost
    chosen[u] = True
    for i in range(n):
        if not chosen[i] and i in A[u] and A[u][i] < d[i]:
            d[i] = A[u][i]


print ans

Solution (Python):

import itertools

n = int(input())
A = []
for i in range(n):
    src = input()
    dst = src.replace('-1', '3000')
    ai = list(map(int, dst.split()))
    A.append(ai)

i = 0
S = 0
G = set()
T = set(range(n))

T.remove(i)
G.add(i)

while len(T) > 0:
    m = 3000
    mg = None
    mt = None
    for g, t in itertools.product(G, T):
        if A[g][t] < m:
            mg = g
            mt = t
            m = A[g][t]
    S += m
    G.add(mt)
    T.remove(mt)

print(S)

Solution (Python):


import sys

def parse():
  A = []
  n = raw_input()
  for line in sys.stdin:
    values = line.split()
    values = [ int(x) for x in values ]
    A.append(values)

  return A 

def prim(cost):
  res = 0
  V = len(cost)
  mincost = [float("inf")] * V
  used    = [False]        * V
  mincost[0] = 0
  while True:
    v = -1
    for u in range(V):
      if not used[u] and \
        (v == -1 or mincost[u] < mincost[v]):
        v = u
    if v == -1:
      break
    used[v] = True
    res += mincost[v]
    for u in range(V):
      if cost[v][u] == -1:
        continue
      mincost[u] = min(mincost[u], cost[v][u])
  return res

if __name__ == "__main__":
  A = parse()
  print prim(A)

Solution (Python):
n = int(raw_input())
A = [0]
NY = range(1, n)
a = [[0 for i in xrange(n)] for j in xrange(n)]
for i in xrange(n):
	a[i] = map(int,raw_input().split())
long = 0
while NY != []:
	amin = 2001
	for i in A:
		for j in NY:
			if 0 <= a[i][j] < amin:
				amin = a[i][j]
				addA = j
	A.append(addA)
	NY.remove(addA)
	long += amin
print long

Solution (Python):

def prim(cost):
    sumcost = 0
    V = len(cost)
    mincost = [float('inf')] * V
    used = [False] * V
    mincost[0] = 0
    while True:
        j = -1
        for i in range(V):
            if not used[i] and (j == -1 or mincost[i] < mincost[j]):
                j = i
        if j == -1:
            break
        used[j] = True
        sumcost = sumcost + mincost[j]
        for i in range(V):
            if cost[i][j] == -1:
                continue
            mincost[i] = min(mincost[i], cost[j][i])
    return sumcost

n = int(raw_input())
A = [0] * n
for i in range(n):
    A[i] = map(int, raw_input().split())

result = prim(A)
print(result)

Solution (Python):
n = int(input())
G = []
for i in range(n):
    G.append(input().split())
    for j in range(len(G[i])):
        G[i][j] = int(G[i][j])

ans = 0
mincost = [2001] * n
flag = [0] * n
mincost[0] = 0
while True:
    v = -1
    for j in range(n):
        if flag[j] != 1 and (v == -1 or mincost[j] < mincost[v]):
            v = j
    if v == -1:
        break
    flag[v] = 1
    ans += mincost[v]
    for j in range(n):
        if G[v][j] == -1: continue
        mincost[j] = min(mincost[j], G[v][j])

print(ans)