#include<bits/stdc++.h>
using namespace std;
typedef long long LL;

const int MAXN = 5000 + 10;

int n,A,k,cnt,tot,ans;
int f[MAXN];
struct Line{
	int x,y;
	int num;
}line[MAXN];

inline int read(){
    int f = 1, x = 0;
    char c = getchar();

    while (c < '0' || c > '9')
    {
        if (c == '-')
            f = -1;
        c = getchar();
    }

    while (c >= '0' && c <= '9')
    {
        x = x * 10 + c - '0';
        c = getchar();
    }

    return f * x;
}

void Add(int a,int b,int ttt){
	line[++cnt].x = a;
	line[cnt].y = b;
	line[cnt].num = cnt;
}

void Doing(){
	for(int i = 1;i <= n; i++)f[i] = i;
	return;
}

bool cmp(Line a,Line b){
	return a.num < b.num;
}

int find(int x){
	if(f[x] == x)return x;
	return f[x] = find(f[x]);
}

void unionn(int x,int y){
	int nx = find(x);
	int ny = find(y);
	if(nx != ny)f[nx] = ny;
}

void Kruskal(){
	for(int i = 1;i <= cnt; i++){
		int nx = find(line[i].x);
		int ny = find(line[i].y);
		if(nx == ny)continue;
		unionn(nx,ny);
		ans += line[i].num;
	}
}

int main(){
	A = read(),n = read();
	for(int i = 1;i <= n; i++){
		for(int j = 1;j <= n; j++){
			k = read();
			if(j < i && k != 0)Add(i,j,k);
		} 
		Add(0,i,A);
	}
	
	Doing();
	sort(line + 1,line + 1 + n,cmp);
	Kruskal();
	
	cout<<ans;
	return 0;
}