走到了一个点才能走（走到）下一个点，即图的性质，以此建图

将其抽象成图，建成图的模型

买了一个东西，买其他东西才有优惠
即走到了一个点才能走（走到）下一个点，即图的性质，以此建图       //点和点之间存优惠的价格
建完图后，已有"买了一个东西，买其他东西才有优惠"的性质，所以在选择方法时就不用考虑是否满足这个性质了

买所有东西花的钱最小
即所有边的边权之和最小
即最小生成树

一条边的边权即从某点指向另一点的优惠价格，所有是有向边，             
但从i到j和从j到i的边权一样，所以就可以看成无向边
kruskal存的是无向边

最小生成树是n个点n-1条边，即sum是n-1个点权之和，但第一个点也要用钱购买，且是原价
所以
1.要么在最后sum+=a
2.要么预处理0号点作为超源，从0向各点连边权为a的边
代码是第二种方法

//

#include<bits/stdc++.h>
using namespace std;
int const M=25e4+7;
int const N=5e2+7;
int a,n,m;
int f[N];
struct node{
    int a,next,len;
    friend bool operator<(node a,node b){
        return a.len < b.len ;
    }
}e[M];
int find(int x){
    return f[x]==x?x:f[x]=find(f[x]); 
}
void merge(int x,int y){
    f[find(x)]=find(y);
}
void kruskal(){
    long long  cnt=0,sum=0;
    for(int i=1;i<=n;++i) f[i]=i;
    sort(e+1,e+m+1);
    for(int i=1;i<=m;++i){
        int c=e[i].a , b=e[i].next ;
        if(find(c)!=find(b)){
            cnt++;
            sum+=e[i].len ;
            merge(c,b);
            if(cnt>=n){  //加了一个超源点，所以一共是n+1个点，n条边 
                break;
            }
        }
    }
    cout << sum;
}
int main(){
    cin >> a >> n;
    for(int i=1;i<=n;++i){
        for(int j=1;j<=n;++j){
            int z; cin >> z;
            if(i<=j) continue;
            e[++m].a =i;e[m].next =j;
            if(z==0) e[m].len =a;     //原来0是指没有优惠的意思，看错了题目 
      else e[m].len =min(a,z);
        }
    }
    for(int i=1;i<=n;++i){
        e[++m].a =0;e[m].next =i;
        e[m].len =a;
    }
    kruskal();
    return 0;
}