Softeer: 복잡한 조립라인1

 

import sys
import collections


K, N = map(int, sys.stdin.readline().split())

grid = []
tran = []

for i in range(N - 1):
    line = list(map(int, sys.stdin.readline().split()))
    grid += line[:K],
    pos = 0
    tran_map = collections.defaultdict(int)

    for j in range(K):
        for k in range(K):
            if j == k:
                continue

            tran_map[(j, k)] = line[K + pos]
            pos += 1

    tran += tran_map,

line = list(map(int, sys.stdin.readline().split()))
grid += line,

for i in range(N - 1):
    for j in range(K):
        mn = grid[i][j]

        for k in range(K):
            if j == k:
                continue
            mn = min(mn, grid[i][k] + tran[i][(k, j)])

        grid[i + 1][j] += mn


print(min(grid[-1]))