#include<bits/stdc++.h>
#define int long long
using namespace std;

const int N=5e2+7;
int fa[N],mp[N][N];
int tot,m,n,cnt,num;
struct Node{
	int h,ver,w;
}e[N*N];

bool cmp(Node x,Node y){
	return x.w<y.w;
}
void add(int u,int v,int w){
	tot++;
	e[tot].h=u;
	e[tot].ver=v;
	e[tot].w=w;
}
int find(int x){
	if(fa[x]==x)return x;
	return fa[x]=find(fa[x]);
}

signed main(){
	ios::sync_with_stdio(NULL);
	cin.tie(0);
	cout.tie(0);
	
	cin>>m>>n;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			cin>>mp[i][j];
			if(mp[i][j]>m){
				num++;
			}
		}
	}
	for(int i=1;i<=n;i++){
		fa[i]=i;
		for(int j=i+1;j<=n;j++){
			add(i,j,mp[i][j]);
			add(j,i,mp[i][j]);
		}
	}
	sort(e+1,e+1+tot,cmp);
	int cnt=1,ans=0;
	for(int i=1;i<=tot-num;i++){
		int u=e[i].h,v=e[i].ver,w=e[i].w;
		if(find(u)==find(v))continue;
		ans+=w;
		cnt++;
		fa[find(u)]=find(v);
	}
	if(cnt==n)cout<<ans+m;
	else cout<<ans+(n-cnt+1)*m;
	
	return 0;
}