RT,懵逼/kk
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int fa[10010],n,m;
struct node{
int no,to,val;
node(int n,int t,int v)
{no=n,to=t,val=v;}
};
vector<node>gra;
int Find(int x)
{
if(fa[x]==x)return x;
else return fa[x]=Find(fa[x]);
}
void Union(int u,int v)
{
int U=Find(u),V=Find(v);
fa[V]=U;
}
bool cmp(node x,node y)
{
return x.val<y.val;
}
int kruskal()
{
for(int p=1;p<=n;p++)
fa[p]=p;
sort(gra.begin(),gra.end(),cmp);
int ans=0;
for(int p=0;p<m;p++)
{
int U=Find(gra[p].no);int V=Find(gra[p].to);
if(U==V)continue;
ans+=gra[p].val;
Union(U,V);
}
return ans;
}
void readnum()
{
cin>>m>>n;
for(int p=1;p<=n;p++)
for(int i=1;i<=n;i++)
{
int x;
cin>>x;
if(p<i&&x)
gra.push_back(node(p,i,x));
}
for(int p=1;p<=n;p++)
gra.push_back(node(0,p,m));
}
int main()
{
readnum();
cout<<kruskal()<<endl;
}