#include<bits/stdc++.h>
using namespace std;
struct edge{
    int st,to,nxt,w;
}e[5005];
int hd[505],tot;
int f[505];
void add(int u,int v,int w){
    e[++tot].to=v;
    e[tot].st=u;
    e[tot].nxt=hd[u];
    e[tot].w=w;
    hd[u]=tot;
}
bool cmp(edge x,edge y){
    return x.w<y.w;
}
int find(int x){
    if (f[x]==x)return x;
    return f[x]=find(f[x]);
}
void join(int u,int v){
    f[find(u)]=find(v);
}
int main(){
    int a,n;cin>>a>>n;
    for (int i=1;i<=n;++i){
        for (int j=1;j<=n;++j){
            int x;cin>>x;
            if (x==0)x=a;
            add(i,j,x);
        }
    }
    for (int i=1;i<=n;++i)f[i]=i;
    sort(e+1,e+tot+1,cmp);
    int ans=0,cnt=0;
    for (int i=1;i<=tot;++i){
        int u=e[i].st,v=e[i].to,w=e[i].w;
        if (cnt==n-1)break;
        if (find(u)==find(v))continue;
        join(u,v);
        ans+=min(w,a),cnt++;
    }
    cout<<ans+a;
}