#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<vector>
#include<map>
using namespace std;
int fa[510],x,i,j,num,k,n,y;
map<int,int> f;
struct no{
	int x,y,t;
}a[510];
bool cmp(no a,no b){
	return a.t<b.t;
}
int find(int x){
	if(fa[x]==x) return fa[x];
	return fa[x]=find(fa[x]);
}
void hb(int x,int y){
	x=find(x);
	y=find(y);
	fa[y]=x;
}
int main(){
	scanf("%d%d",&k,&n);
	for(i=1;i<=n;i++) fa[i]=i;
	for(i=1;i<=n;i++)
	  for(j=1;j<=n;j++)
	    scanf("%d",&x),a[n*(i-1)+j].x=i,a[n*(i-1)+j].y=j,a[n*(i-1)+j].t=x+(!x)*k;
	sort(a+1,a+1+n*n,cmp);
	for(i=1;i<=n*n;i++){
		x=find(a[i].x);y=find(a[i].y);
		if(x!=y) fa[y]=x,num+=a[i].t+(!f[x])*k,f[x]=1;
	}
	for(i=1;i<=n;i++)
	  if(fa[i]==i&&!f[i]) num+=k;
	printf("%d",num);
	return 0;
}
/*
3 3
0 2 4
2 0 2
4 2 0

2 2
0 1
2 0
*/