//Floyd算法 //逆序加入节点
import java.io.*;

public class Main{
    static StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));

    static int n,a[][];
    static long sum;
    public static void main(String[] args) throws IOException{
        n = next();
        a = new int[n][n];
        if(n == 1) {
            System.out.println(0);
            return; //特例
        }
        for(int i = 0; i < n; i ++) {//输入
            for(int v = 0; v < n; v ++) {
                a[i][v] = next();
            }
        }
        int x = n - 1;
        for(int y = n - 1; y > 0; y --, x --) {//迭代以x为起点的矩阵
            update(y);
            //累加到sum中
            for(int b = x; b < n; b ++) {
                for(int c = x; c < n; c ++) {
                    sum += a[b][c];
                }
            }
        }

        System.out.println(sum);
    }
    static void update(int v) {
        for(int x = 0; x < n; x ++) {
            for(int y = 0; y < n; y ++) {
                if(a[x][y] > a[x][v] + a[v][y] ) {
                    a[x][y] = a[x][v] + a[v][y]; //x->v->y 以v为中转节点迭代
                }
            }
        }
    }

    static int next() throws IOException{
        in.nextToken();
        return (int)in.nval;
    }
}