改成$O（N^4）$只得了8分

#include<bits/stdc++.h>
#define int long long
#define maxn 100+10
#define inf 0x3f3f3f3f

using namespace std;

int n,m;
int g[maxn][maxn];
int f[maxn][maxn];
int ans=INT_MAX;

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;
}

inline int floyd(){
	for(register int i(1);i<=n;++i) for(register int j(1);j<=n;++j) f[i][j]=g[i][j];
	for(register int k(1);k<=n;++k){
		for(register int i(1);i<=n;++i){
			for(register int j(1);j<=n;++j){
				f[i][j]=min(f[i][k]+f[k][j],f[i][j]);
			}
		}
	}
	int cnt=0;
	for(register int i(1);i<=n;++i){
		for(register int j=1;j<=i;++j){
			cnt+=f[i][j];
		}
	}
	return cnt;
}

inline int floyd1(int x,int y){
	for(register int i(1);i<=n;++i) for(register int j(1);j<=n;++j) f[i][j]=g[i][j];
	for(register int i(1);i<=n;++i){
		for(register int j(1);j<=n;++j){
			f[i][j]=min(f[i][j],f[i][x]+f[x][j]);
		}
	}
	for(register int i(1);i<=n;++i){
		for(register int j(1);j<=n;++j){
			f[i][j]=min(f[i][j],f[i][y]+f[y][j]);
		}
	}
	int cnt=0;
	for(register int i(1);i<=n;++i){
		for(register int j=1;j<=i;++j){
			cnt+=f[i][j];
		}
	}
	return cnt;
}

signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
//	n=read(),m=read();
	scanf("%lld %lld",&n,&m);
	for(register int i(1);i<=n;++i) for(register int j(1);j<=n;++j){
		if(i==j) g[i][j]=0;
		else g[i][j]=inf;
	}
	for(register int i=(1);i<=m;++i){
		int x,y,w;
		scanf("%lld %lld %lld",&x,&y,&w); 
//		x=read(),y=read(),w=read(); 
		g[x][y]=min(g[x][y],w);
		g[y][x]=min(g[y][x],w);
//		f[x][y]=min(f[x][y],w);
//		f[y][x]=min(f[y][x],w);
	}
	ans=floyd();
	for(register int i(1);i<=n;++i){
		for(register int j(1);j<=n;++j){
//			if(g[i][j]!=0){
				int t=g[i][j];
				g[i][j]=g[j][i]=0;
				ans=min(ans,floyd1(i,j));
				g[i][j]=g[j][i]=t;
//			}
		}
	}
	printf("%lld\n",ans);
	return 0;
}