#!/usr/bin/python3

import networkx
import sys

matrix=[]
f=open(sys.argv[1])
for line in f:
    line=line.rstrip()
    if len(line)==0:
        continue
    matrix.append (list(map(int, line.split(","))))

matrix_size=len(matrix)

def row_col_to_vertex_n(row, col):
    assert row<matrix_size
    assert col<matrix_size
    return row*matrix_size+col

def vertex_n_to_row_col(n):
    row=n // matrix_size
    col=n % matrix_size
    assert row<matrix_size
    assert col<matrix_size
    return row, col

# must be larger that row_col_to_vertex_n(matrix_size,matrix_size)
special_vertex_n=matrix_size**2
#print (f"{special_vertex_n=}")
#print (f"{row_col_to_vertex_n(matrix_size-1,matrix_size-1)=}")
assert row_col_to_vertex_n(matrix_size-1,matrix_size-1) < special_vertex_n

def do_all(PE_problem):
    vertices_total=special_vertex_n+matrix_size

    G = networkx.DiGraph()
    for row in range(matrix_size):
        G.add_weighted_edges_from([(special_vertex_n+row, row_col_to_vertex_n(row, 0), matrix[row][0])])

    for row in range(matrix_size):
        for col in range(matrix_size):
            # down
            if row!=matrix_size-1:
                vertex_n_src=row_col_to_vertex_n(row, col)
                vertex_n_dst=row_col_to_vertex_n(row+1, col)
                G.add_weighted_edges_from([(vertex_n_src, vertex_n_dst, matrix[row+1][col])])
            # right
            if col!=matrix_size-1:
                vertex_n_src=row_col_to_vertex_n(row, col)
                vertex_n_dst=row_col_to_vertex_n(row, col+1)
                G.add_weighted_edges_from([(vertex_n_src, vertex_n_dst, matrix[row][col+1])])
            if PE_problem in [82,83]:
                # up
                if row!=0:
                    vertex_n_src=row_col_to_vertex_n(row, col)
                    vertex_n_dst=row_col_to_vertex_n(row-1, col)
                    G.add_weighted_edges_from([(vertex_n_src, vertex_n_dst, matrix[row-1][col])])
            if PE_problem==83:
                # left
                if col!=0:
                    vertex_n_src=row_col_to_vertex_n(row, col)
                    vertex_n_dst=row_col_to_vertex_n(row, col-1)
                    G.add_weighted_edges_from([(vertex_n_src, vertex_n_dst, matrix[row][col-1])])

    fw = networkx.floyd_warshall(G, weight="weight")
    results = {a: dict(b) for a, b in fw.items()}

    #print (results)
    # PE 81 and PE 82
    if PE_problem in [81, 83]:
        print (results[special_vertex_n][row_col_to_vertex_n(matrix_size-1,matrix_size-1)])
    if PE_problem==82:
        rt=[]
        for row1 in range(matrix_size):
            for row2 in range(matrix_size):
                rt.append (results[special_vertex_n+row1][row_col_to_vertex_n(row2,matrix_size-1)])
        print (min(rt))

print ("*** PE 81")
do_all(81)
print ("*** PE 82")
do_all(82)
print ("*** PE 83")
do_all(83)