#include<bits/stdc++.h>
using namespace std;
struct edge{
	int from,to,w;
}a[250001];
inline int read(){
    int x=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){
        if(ch=='-')
            f=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        x=(x<<1)+(x<<3)+(ch^48);
        ch=getchar();
    }
    return x*f;
}
int sum,fa[501];
bool cmp(edge a,edge b)
{
	return a.w<b.w;
}
int getfa(int x)
{
	if(fa[x]==x)
	return x;
	return fa[x]=getfa(fa[x]);
}

int main()
{
	int n,m,cnt=1,cot=0;
	cin>>n>>m;
	for(int i=1;i<=m;i++)
	{
		for(int j=1;j<=m;j++) 
		{
			if(j==i)
			{
				read();
				fa[i]=i;
				continue;
			}
			a[cnt].w=read();
			if(a[cnt].w==0||a[cnt].w>=n)
			continue;
			a[cnt].to=j;
			a[cnt++].from=i;
		}
	}
	cnt--;
	sort(a+1,a+cnt+1,cmp);
	for(int i=1;i<=cnt&&cot<=m-1;i+=2)
	{
		if(getfa(a[i].from)!=getfa(a[i].to))
		{
			cot++;
			sum+=a[i].w;
			fa[fa[a[i].from]]=fa[a[i].to];
		}
	}
	cout<<sum+(m-cot)*n;
	return 0;
}