#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10;
const int M=1e6+10;
int a,b,s[M],cnt=0,ans=0,m=0;
struct edge{
    int u,v,w;
}e[M];
bool cmp(edge x,edge y){
    return x.w<y.w;
}
int find(int x){
    if(x!=s[x]) s[x]=find(s[x]);
    return s[x];
}
int main()
{
    cin>>a>>b;
    for(int i=0;i<=b;i++)s[i]=i;
    for(int i=1;i<=b;i++){
        e[m].u=0;
        e[m].v=i;
        e[m].w=a;
        m++;
    }
    for(int i=1;i<=b;i++){
        for(int j=1;j<=b;j++){
            int f;
            cin>>f;
            if(f!=0){
                e[m].u=i;
                e[m].v=j;
                e[m].w=f;
                m++;
            }
        }
    }
    sort(e,e+m,cmp);

    for(int i=1;i<=m;i++){
        int u=find(e[i].u);
        int v=find(e[i].v);
        int w=e[i].w;
        if(u==v) continue;
        s[u]=v;
        ans+=w;
    }
    cout<<ans;
    return 0;
}