#include<bits/stdc++.h>
using namespace std;
struct edge{
	int u,v,k;
}e[2010];
int a,b,cnt;
int f[2010];
inline int find(int x){
	if(x==f[x]) return x;
	return f[x]=find(f[x]);
}
inline bool cmp(edge x,edge y){
	return x.k<y.k;
}
int main(){
	scanf("%d%d",&a,&b);
	for(int i=1;i<=b;i++){
		for(int j=1;j<=b;j++){
			int x;
			scanf("%d",&x);
			if(j>i){
				if(x==0||x>a){
					continue;
				}
				else{
					e[++cnt].u=i;
					e[cnt].v=j;
					e[cnt].k=x;
				}
			}
		}
	}
	sort(e+1,e+1+cnt,cmp);
	for(int i=1;i<=b;i++){
		f[i]=i;
	}
	int nd=0;
	int i=1;
	int ans=0;
	for(int i=1;i<=cnt;i++){
		int l=find(e[i].u),r=find(e[i].v);
		if(l==r){
			continue;
		}
		ans+=e[i].k;
		f[l]=find(f[r]);
		nd++;
	}
	if(nd<b) ans+=(b-nd)*a;
	printf("%d",ans);
	return 0;
}