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):
n = int(input())
edgeList = []
for i in range(n):
    a = list(map(int, input().split()))
    for j in range(i):
        if a[j] != -1:
            edgeList.append([a[j], i, j])
rootList = [-1]*n
sumLength = 0

def getRoot(x):
    r = rootList[x]
    if r < 0:
        rootList[x] = x
    elif r != x:
        rootList[x] = getRoot(r)
    return rootList[x]
        

edgeList.sort(key=lambda x: x[0])
for e in edgeList:
    x = getRoot(e[1])
    y = getRoot(e[2])
    if x != y:
        sumLength += e[0]
        rootList[x] = rootList[y] = min(x, y)
print(sumLength)

Solution (Python):
INFTY = 1 << 21
WHITE = 0
GRAY = 1
BLACK = 2

n = int(input())
M = [list(map(int, input().split())) for i in range(n)]

d = [INFTY for i in range(n)]
p = [-1 for i in range(n)]
color = [WHITE for i in range(n)]

for i in range(n):
    for j in range(n):
        if (M[i][j] == -1):
            M[i][j] = INFTY

def prim():
    global M, d, p, color
    d[0] = 0
    while(1):
        minv = INFTY
        u = -1
        for i in range(n):
            if (minv > d[i] and color[i] != BLACK):
                u = i
                minv = d[i]
        if (u == -1):
            break
        color[u] = BLACK
        for v in range(n):
            if (color[v] != BLACK and M[u][v] != INFTY):
                if (d[v] > M[u][v]):
                    d[v] = M[u][v]
                    p[v] = u
                    color[v] = GRAY
    
    return sum([M[i][p[i]] for i in range(n) if p[i] != -1])

print(prim())

Solution (Python):
inf = float('inf')
n = int(input())
a = []

for i in range(n):
    line = list(map(int, input().split()))
    for i in range(len(line)):
        if line[i] == -1:
            
            line[i] = inf
    a.append(line)

checked = [False] * n
d = [inf] * n
checked[0] = True
ans = 0
nxt = 0

for i in range(n - 1):
    for j in range(n):
        if a[nxt][j] < d[j]:
            d[j] = a[nxt][j]

    min_n = 0
    min_w = inf

    for j in range(n):
        if not checked[j] and d[j] < min_w:
            min_n = j
            min_w = d[j]

    checked[min_n] = True
    nxt = min_n
    ans += min_w

print(ans)

Solution (Python):
import itertools

n = int(input())
A = []
for i in range(n):
    line = input()
    A.append([int(x) for x in line.split()])


V = set(range(n))
Vnew = {0}  
weights = []

while V != Vnew:
    T = V - Vnew
    minw = float('inf')
    for u, v in itertools.product(Vnew, T):
        w = A[u][v]
        if w != -1 and minw > w:
            e = (u, v)
            minw = w
    Vnew.add(e[1])
    weights.append(minw)

print(sum(weights))

Solution (Python):



if __name__ == '__main__':

    n = int(input())
    M = [list(map(int, input().split(" ")[1:])) for _ in range(n)]

    color = [0] * n
    d = [float("inf")] * n
    p = [None] * n

    def prim():
        d[0] = 0
        p[0] = -1

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

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

            color[u] = 2

            for v in range(n):
                if color[v] != 2 and M[u][v] != -1:
                    if M[u][v] < d[v]:
                        d[v] = M[u][v]
                        p[v] = u
                        color[v] = 1

    prim()
    sum = 0
    for i in range(n):
        if p[i] != -1:
            sum += M[i][p[i]]

    print(sum)

Solution (Python):
INF = float("inf")
def MAIN():
    n = int(input())
    M = [[INF] * 101 for _ in range(101)]
    for i in range(n):
        for j, e in enumerate(map(int, input().split())):
            if e != -1:
                M[i][j] = e
    def prim():
        d = [INF] * n
        t = [-1] * n
        color = [0] * n
        d[0] = 0
        while True:
            minv = INF
            u = -1
            for i in range(n):
                if minv > d[i] and color[i] != 2:
                    u = i
                    minv = d[i]
            if u == -1:
                break
            color[u] = 2
            for v in range(n):
                if color[v] != 2 and d[v] > M[u][v]:
                    d[v] = M[u][v]
                    t[v] = u
                    color[v] = 1
        return sum(d)
    print(prim())
MAIN()

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

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

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

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())
edgeList=[]
for i in range(n):
 a=list(map(int,input().split()))
 for j in range(i):
  if a[j]>=0:edgeList+=[(a[j],i,j)]
rootList=[-1]*n
sumLength=0
def getRoot(x):
 r=rootList[x]
 if r<0:rootList[x]=x
 elif r!=x:rootList[x]=getRoot(r)
 return rootList[x]
edgeList.sort(key=lambda x:x[0])
for e in edgeList:
 x=getRoot(e[1])
 y=getRoot(e[2])
 if x!=y:
  sumLength+=e[0]
  rootList[x]=rootList[y]=min(x,y)
print(sumLength)

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

a = []
for i in range(n):
    a.append(list(map(int, input().split())))

ans = 0
mincost = [2001] * n
flag = [0] * n
mincost[0] = 0

while 1:
    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 a[v][j] == -1:
            continue
        mincost[j] = min(mincost[j], a[v][j])
print(ans)

Solution (Python):
INF = 1e9

n = int(input())

a = []
for i in range(n):
    a.append(list(map(int, input().split())))

def prim(n):
    flag = [0] * n
    d = [INF] * n
    d[0] = 0
    p = [-1] * n

    while True:
        min_cost = INF
        
        for i in range(n):
            if flag[i] != 1 and d[i] < min_cost:
                min_cost = d[i]
                u = i
        if min_cost == INF:
            break
        flag[u] = 1
        
        for v in range(n):
            if flag[v] != 1 and a[u][v] != -1:
                if a[u][v] < d[v]:
                    d[v] = a[u][v]
                    p[v] = u
    return sum(d)

print(prim(n))

Solution (Python):
from enum import Enum, auto
class Color(Enum):
    WHITE = auto()
    GRAY = auto()
    BLACK = auto()

n = int(input())
M = []
for i in range(n):
    arr = [int(x) for x in input().split(' ') if x != '']
    M.append(arr)
colors = []
d = []
p = [0 for i in range(n)]

INFTY = 2001
def prim():
    global d
    colors = [Color.WHITE for i in range(n)]
    d = [INFTY for i in range(n)]

    d[0] = 0 
    p[0] = -1 

    while True:
        mincost = INFTY
        u = 0
        for i in range(n):
            if colors[i] != Color.BLACK and d[i] < mincost:
                mincost = d[i]
                u = i
        if mincost == INFTY: break

        colors[u] = Color.BLACK
        for v in range(n):
            if colors[v] != Color.BLACK and M[u][v] != -1:
                if M[u][v] < d[v]:
                    d[v] = M[u][v]
                    p[v] = u
                    colors[v] = Color.GRAY

prim()
print(sum(d))

Solution (Python):
import heapq


class MST:
    """Given weighted graph, find minimum spanning tree.

    >>> mst = MST([[-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]]);
    >>> mst.weight()
    5
    """
    MAX_WEIGHT = 2001

    def __init__(self, graph):
        self.graph = graph
        self.size = len(graph)
        self.tree = []
        self._search()

    def weight(self):
        return sum([self.graph[i][j] for i, j in self.tree])

    def _search(self):
        visited = [0]

        while len(visited) < self.size:
            h = []
            for node in visited:
                for i, w in enumerate(self.graph[node]):
                    if w == -1:
                        continue
                    if i in visited:
                        continue
                    heapq.heappush(h, (w, node, i))

            weight, src, dst = heapq.heappop(h)
            visited.append(dst)
            self.tree.append((src, dst))


def run():
    n = int(input())

    nodes = []
    for _ in range(n):
        nodes.append([int(i) for i in input().split()])

    mst = MST(nodes)
    print(mst.weight())


if __name__ == '__main__':
    run()

Solution (Python):
n = int(input())
sides = []
ws = []
ss = []
for _ in range(n):
    sides.append(list(map(int,input().split())))
for i in range(n):
    for j in range(i+1,n):
        if sides[i][j] >= 0:
            ws.append([sides[i][j],i,j])
rs = [(i) for i in range(n)]
def root(x):
    global rs
    if rs[x] == x:
        return(x)
    else:
        return(root(rs[x]))
ws.sort()
ans = 0
while(len(ws)):
    if root(ws[0][1]) != root(ws[0][2]):
        ans += ws[0][0]
        rs[root(rs[ws[0][2]])] = root(ws[0][1])
        ss.append(ws[0])
    del(ws[0])
print(ans)

Solution (Python):
import sys
INF = float('inf')
n = int(input())
adja_matrix = [[int(i) for i in line.split()] for line in sys.stdin.read().splitlines()]
condition = ['INIT'] * n
distance = [INF] * n
p = [0] * n
distance[0] = 0
p[0] = -1

while True:
    mincost = INF
    for i in range(n):
        if condition[i] != 'FINISH' and distance[i] < mincost:
            mincost = distance[i]
            u = i

    if mincost == INF:
        break

    condition[u] = 'FINISH'

    for v in range(n):
        if condition[v] != 'FINISH' and adja_matrix[u][v] != -1:
            if adja_matrix[u][v] < distance[v]:
                distance[v] = adja_matrix[u][v]
                p[v] = u
                condition[v] = 'CHECK'

sum = 0
for i in range(n):
    if p[i] != -1:
        sum += adja_matrix[i][p[i]]

print(sum)

Solution (Python):
n = int(input())
m = []

for _ in range(n):
    tmp = [int(x) for x in input().split()]
    m.append(tmp)


edge_list = [] 
j = 1
for i in range(n-1):
    for k,x in enumerate(m[i][j:]):
        if x != -1:
            edge_list.append((x,i,k+j))
        else:
            pass
    j += 1
edge_list.sort()

root_list = [i for i in range(n)]

def root(x):
    path_to_root = []
    while root_list[x] != x:
        path_to_root.append(x)
        x = root_list[x]
    for node in path_to_root:
        root_list[node] = x
    return x

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

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

cost = 0
for x in edge_list:
    w,p,q = x
    if is_same_root(p,q):
        continue
    else:
        cost += w
        unite(p,q)

print(cost)

Solution (Python):




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

    def root(self, x):
        path_to_root = []
        while self.parent[x] != x:
            path_to_root.append(x)
            x = self.parent[x]
        for node in path_to_root:
            self.parent[node] = x  
        return x

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

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

    def __str__(self):
        groups = {}
        for x in range(self.N):
            root = self.root(x)
            if root in groups.keys():
                groups[root].append(x)
            else:
                groups[root] = [x]
        result = ""
        for root in groups.keys():
            result += str(groups[root]) + "\n"
        return result






def kruskal(num_vertices, edges):
    total_weight = 0
    edges.sort(key=lambda e: e[2])
    u = UnionFind(num_vertices)
    for e in edges:
        x = e[0]
        y = e[1]
        weight = e[2]
        if u.same(x, y):
            continue
        u.unite(x, y)
        total_weight += weight
    return total_weight


n = int(input())
edges = []
for i in range(n):
    row = list(map(int, input().split()))
    for j in range(i, n):
        if row[j] != -1:
            edges.append([i, j, row[j]])
print(kruskal(n, edges))

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

INF = 2147483647
G = [[INF for j in range(n)] for i in range(n+1)]
check = [0 for i in range(n)]


def prim():
    d = [INF for i in range(n)]
    p = [-1 for i in range(n)]
    d[0] = 0
    cost = 0

    while True:
        min_cost = INF
        for i in range(n):
            if check[i] != 2 and d[i] < min_cost:
                min_cost = d[i]
                u = i

        if min_cost == INF:
            break

        cost += d[u]
        check[u] = 2

        for v in range(n):
            if check[v] != 2 and G[u][v] != INF:
                if G[u][v] < d[v]:
                    d[v] = G[u][v]
                    p[v] = u
                    check[v] = 1

    return cost


def main():
    for i in range(n):
        data = list(map(int, input().split()))
        for j in range(n):
            if data[j] != -1:
                G[i][j] = data[j]

    print(prim())


if __name__ == '__main__':
    main()

Solution (Python):
class UnionFindTree:
    """
        Disjoint set data structure
        Union-Find tree
        complexity:
            init: O(n)
            find, unite, same: O(alpha(n))
    """
    def __init__(self, n):
        self.par = list(range(n))
        self.rank = [0] * 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, y = self.find(x), self.find(y)
        if x == y:
            return
        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 same(self, x, y):
        return self.find(x) == self.find(y)


class Kruskal:
    """
        Kruskal's algorithm: find Minimum Spanning Tree
        complexity:
            O(E logV)
    """
    def __init__(self, V, E, start=0, INF=10**9):
        """
        :param V: the number of vertices
        :param E:  adjacency list (undirected graph)
        :param start:
        :param INF:
        """
        self.kruskal(V, E)

    def kruskal(self, V, E):
        edges = []
        for v1 in range(V):
            for v2, cost in E[v1]:
                if v1 < v2:
                    edges.append((cost, v1, v2))
        edges.sort(reverse=True)
        self.mincost = 0
        self.min_spanning_tree = []
        uf = UnionFindTree(V)
        while len(self.min_spanning_tree) < V - 1:
            cost, v1, v2 = edges.pop()
            if not uf.same(v1, v2):
                self.mincost += cost
                uf.unite(v1, v2)
                self.min_spanning_tree.append((v1, v2, cost))

    def min_cost(self):
        return self.mincost

    def get_min_spanning_tree(self):
        return sorted(self.min_spanning_tree)


V = int(input())
edges = [[] for _ in range(V)]
for i in range(V):
    for j, d in enumerate(map(int, input().split())):
        if d != -1:
            edges[i].append((j, d))
mst = Kruskal(V, edges)
print(mst.min_cost())

Solution (Python):

inf = 1000000
n = int(input())
mtrx = []
for i in range(n):
    nums = list(map(int,input().split()))
    col = []
    for j in range(n):
        if nums[j] == -1:
            col.append(inf)
        else:
            col.append(nums[j])
    mtrx.append(col)

        
d = [inf for i in range(n)]
p = [-1 for i in range(n)]
color = ["white" for i in range(n)]
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))

Solution (Python):
import sys
    
global status, d
status = {}
d=0

def mst(p1, GRAPH):
    global status
    
    edge={}
    total = 0
    mini = 0
    while True:
        status[p1]=True
        for p2 in range(len(status)):
            if status[p2]==False and GRAPH.has_key((p1,p2)):
                edge[(p1, p2)]=GRAPH[(p1, p2)]
        mini=1000000
        for key, value in edge.items():
            if status[key[1]]==True:
                del edge[key]
                continue
            if value <mini:
                key0 = key
                mini = value
        if mini!=1000000:
            total+=mini
            p1=key0[1]
        else:
            break
    
    return total

n = int(raw_input())
x = {}
for i in range(n):
    seq = map(int,raw_input().split())
    for j in range(n):
        tmp = seq[j]
        if tmp != -1:
            x[(i, j)]=tmp
    status[i] = False

print mst(0, x)

Solution (Python):

from __future__ import division, print_function
from sys import stdin, maxint


def main():
    num = int(stdin.readline())

    M = []
    for _ in xrange(num):
        M.append([int(s) for s in stdin.readline().split()])

    g = set(xrange(1, num+1))
    index = g.pop()
    h = {index}
    gravity = 0

    while g:
        minimum = maxint
        for j in h:
            mj = M[j-1]
            for i in g:
                if 0 <= mj[i-1] < minimum:
                    index = i
                    minimum = mj[i-1]
        h.add(index)
        g.remove(index)
        gravity += minimum

    print(gravity)


main()

Solution (Python):

from __future__ import division, print_function
from sys import stdin, maxint


def main():
    num = int(stdin.readline())

    M = []
    for _ in xrange(num):
        M.append([int(s) for s in stdin.readline().split()])

    g = set(xrange(1, num+1))
    index = g.pop()
    h = {index}
    weight = 0

    while g:
        minimum = maxint
        for j in h:
            mj = M[j-1]
            for i in g:
                if 0 <= mj[i-1] < minimum:
                    index = i
                    minimum = mj[i-1]
        h.add(index)
        g.remove(index)
        weight += minimum

    print(weight)


main()

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

n = int(input())
g = [[] for _ in range(n)]

for i in range(n):
    for j,k in enumerate(map(int,input().split())):
        if k != -1:
            g[i].append((j,k))


ocupied = [0]*n
que = [(j,k) for k,j in g[0]] 


ocupied[0] = 1
heapify(que)

ans = 0
while que:
    cv,v = heappop(que)
    
    if ocupied[v]: 
        continue
    ocupied[v] = 1
    ans += cv
    for j,k in g[v]:
        if ocupied[j]:
            continue
        heappush(que,(k,j))
    
print(ans)

Solution (Python):
class UnionFind:
    def __init__(self, n: int):
        self.nodes = n
        self.parents = [-1] * n
        self.rank = [0] * n

    
    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    
    def unite(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        if self.rank[x] < self.rank[y]:
            self.parents[y] += self.parents[x]
            self.parents[x] = y
        else:
            self.parents[x] += self.parents[y]
            self.parents[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

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

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


def kruskal(n: int, edges: list):
    """
    n: count of nodes
    edges: list of edges, format: (node1,node2,weight)
    """
    union = UnionFind(n + 1)  
    mst_sum = 0
    mst = []
    for edge in edges:
        n1, n2, w = edge
        if not union.same(n1, n2):
            union.unite(n1, n2)
            mst_sum += w
            mst.append(edge)
    return mst, mst_sum


n = int(input())
graph_table = []

for _ in range(n):
    graph_table.append([int(i) for i in input().split()])

edges = []

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


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

_, mst_sum = kruskal(n, edges)
print(mst_sum)

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

import heapq

def prim(N):
    d[1] = 0
    p[1] = -1
    u = 1

    while True:
        mincost = 3000
        for i in range(1, N+1):
            if color[i] != 2 and d[i] < mincost:
                mincost = d[i]
                u = i
        if mincost == 3000:
            break

        color[u] = 2

        for v in range(1, N+1):
            if color[v] != 2 and M[u][v] != 3000:
                if M[u][v] < d[v]:
                    d[v] = M[u][v]
                    p[v] = u
                    color[v] = 1
    
    sum_ = 0
    for i in range(1, N+1):
        if p[i] != -1:
            sum_ += M[i][p[i]]

    return sum_




N = int(input())
color = [0] * (N+1)
counter = 0
d = [3000] * (N+1) 
p = [-1] * (N+1)
M = [[3000] * (N+1) for i in range(N+1)]

for i in range(1, N+1):
    A = list(map(int, input().split()))
    for j, v in enumerate(A):
        if v != -1:
            M[i][j+1] = v

print(prim(N))

Solution (Python):
import sys, os, math, bisect, itertools, collections, heapq, queue, copy, array





sys.setrecursionlimit(10000000)

ii = lambda: int(sys.stdin.buffer.readline().rstrip())
il = lambda: list(map(int, sys.stdin.buffer.readline().split()))
fl = lambda: list(map(float, sys.stdin.buffer.readline().split()))
iln = lambda n: [int(sys.stdin.buffer.readline().rstrip()) for _ in range(n)]

iss = lambda: sys.stdin.buffer.readline().decode().rstrip()
sl = lambda: list(map(str, sys.stdin.buffer.readline().decode().split()))
isn = lambda n: [sys.stdin.buffer.readline().decode().rstrip() for _ in range(n)]

lcm = lambda x, y: (x * y) // math.gcd(x, y)

MOD = 10 ** 9 + 7
INF = float('inf')


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

    def root(self, N):
        if self.tree[N] == N:
            return N
        else:
            self.tree[N] = self.root(self.tree[N])
            return self.tree[N]

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

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


def main():
    if os.getenv("LOCAL"):
        sys.stdin = open("input.txt", "r")

    N = ii()
    uf = UnionFind(N)
    ret = 0
    cost = []
    for i in range(N):
        D = il()
        for j in range(N):
            if D[j] != -1:
                cost.append((D[j], i, j))
    else:
        cost.sort()
        for c, v1, v2 in cost:
            if not uf.same(v1, v2):
                ret += c
                uf.unite(v1, v2)
        print(ret)


if __name__ == '__main__':
    main()

Solution (Python):
n = int(input())
INFTY = 10**5
WHITE = 0
GRAY = 1
BLACK = 2

A = [[ int(row) if row != "-1" else INFTY for row in input().split()] for i in range(n)]

def prim(A, st):
    colors = [WHITE] * n
    colors[st] = BLACK
    T = [st]
    total_weights = 0
    
    while len(T) < n:
    
        current_min = INFTY
        next_add = st
        for node_inT in T:
            for v in range(n):
                if colors[v] == WHITE and A[node_inT][v] < current_min:
                    current_min = A[node_inT][v]
                    next_add = v

        total_weights += current_min
        T.append(next_add)
        colors[next_add] = BLACK
    
    return total_weights

MST = [0] * n
for i in range(n):
    MST[i] = prim(A, i)

print(min(MST))

Solution (Python):
def prim():
    visited = [0]*n
    d = [float("inf")]*n
    p = [-1]*n
    
    d[0] = 0

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

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

        visited[u] = 2

        for v in range(n):
            if visited[v] != 2 and M[u][v] != float("inf"):
                if d[v] > M[u][v]:
                    d[v] = M[u][v]
                    p[v] = u
                    visited[v] = 1
                
    ans = 0
    for i,j in enumerate(p[1:], start=1):
        ans += M[i][j]
        
    return ans


n = int(input())
M = []

for _ in range(n):
    M.append([x if x != -1 else float("inf") for x in map(int, input().split())])


print(prim())

Solution (Python):
n=int(input())
inf=10000
color=["white" for i in range(n)]
p=[-1 for i in range(n)]
d=[inf for i in range(n)]
M=[[] for i in range(n)]


for i in range(n):
    tmp=list(map(int,input().split()))
    for j in range(n):
        if tmp[j]==-1:
            M[i].append(inf)
        else:
            M[i].append(tmp[j])

def prim():
    d[0]=0
    while True:
        mincost=inf
        for i in range(n):
            if mincost>d[i] and color[i]!="black":
                mincost=d[i]
                u=i
        if mincost==inf:
            break
        color[u]="black"
        for j in range(n):
            if color[j]!="black" and M[u][j]!=inf:
                if M[u][j]<d[j]:
                    d[j]=M[u][j]
                    p[j]=u
                    color[j]="gray"

prim()
print(sum(d))

Solution (Python):
n = int(input())
A = [list(map(int, input().split())) for i in range(n)]

isVisited = [False] * n
d = [0] + [2001] * (n - 1)
p = [-1] * n

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

    if mincost == 2001:
        break

    isVisited[u] = True

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

print(sum(d))

Solution (Python):
def prim(n,M):
    d = [None]*n
    p = [None]*n
    searched = [0]*n
    
    for i in range(n):
        d[i] = float("inf")
        p[i] = -1
    
    d[0] = 0
    
    while True:
        minv = float("inf")
        u = -1
        for i in range(n):
            if minv > d[i] and not searched[i]:
                u = i
                minv = d[i]
        
        if u == -1:
            break
        searched[u] = 1
        for v in range(n):
            if (not searched[v]) and M[u][v] != -1:
                if d[v] > M[u][v]:
                    d[v] = M[u][v]
                    p[v] = u

    s = 0
    for i in range(n):
        if p[i] != -1:
            s += M[i][p[i]]
    return print(s)

n = int(input())
M = [list(map(int,input().split())) for _ in range(n)]
prim(n,M)

Solution (Python):
def prim(n, cost):
    mincost = [float("inf")]*n
    used = [False] * n
    mincost[0] = 0
    res = 0
    cnt = 1
    while True:
        u = -1
        for i in range(n):
            if (not used[i]) and (u == -1 or mincost[i] < mincost[u]):
                u = i
        if u == -1:
            break
        used[u] = True
        res += mincost[u]
        for v in range(n):
            if cost[u][v] != -1:
                mincost[v] = min(mincost[v], cost[u][v])
    return res


def main():
    n = int(input())
    g = []
    for _ in range(n):
        g.append(list(map(int, input().split())))
    print(prim(n, g))



if __name__ == '__main__':
    main()

Solution (Python):
N = int(input())
P = [i for i in range(N)]
weight = []

def root(x):
    path_to_root = []
    while P[x] != x:
        path_to_root.append(x)
        x = P[x]
    for node in path_to_root:
        P[node] = x
    return x

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

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

for i in range(N):
    lis = list(map(int,input().split()))
    for j in range(N):
        if lis[j] == -1:
            continue
        else:
            weight.append([lis[j],i,j])

weight.sort()
length = len(weight)
k = 0
total_weight = 0

for k in range(length):
    if is_same_set(weight[k][1],weight[k][2]):
        continue
    else:
        unite(weight[k][1],weight[k][2])
        total_weight += weight[k][0]

print(total_weight)

Solution (Python):
def root(x):
    path_to_root = []
    while P[x] != x:
        path_to_root.append(x)
        x = P[x]
    for node in path_to_root:
        P[node] = x
    return x
def is_same_set(x,y):
    return root(x) == root(y)
def unite(x,y):
    P[root(x)] = root(y)
    
    

n= int(input())
a=[]
P=[i for i in range(n)]

for i in range(n):
    temp= list(map(int,input().split()))
    for j in range(i,n):
        if temp[j] != -1:
            a.append([temp[j], i, j])
a.sort()
ans=0
for i in a:
    if not(is_same_set(P[i[1]],P[i[2]])):
        unite(i[1],i[2])
        ans+= i[0]
print(ans)

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

ds=[i for i in range(n)]
def root(x):
  path_to_root = []
  while ds[x] != x:
    path_to_root.append(x)
    x = ds[x]
  for i in path_to_root:
    ds[i] = x
  return x
def same(x,y):
  return root(x) == root(y)
def unite(x,y):
  ds[root(x)] = root(y)

p=[] 
for i in range(n):
  a=list(map(int,input().split()))
  for j in range(i+1,n):
    if a[j]!=-1: p.append([a[j],i,j])
p.sort(key=lambda x:x[0])
ans=0
for i in p:
  if same(i[1],i[2]): continue
  unite(i[1],i[2])
  ans+=i[0]
print(ans)