一个用最短路树做包含 $x$ 简单环长最小值的，正解是 $O(n^3\log n)$ 的（$m$ 与 $n^2$ 同阶）。

#include<bits/stdc++.h>
#define Maxn 1005  
using namespace std;
struct Edge {
	int u,v,w;
	bool operator<(const Edge&is)
		const{return w > is.w;}
} e[Maxn*Maxn];
int tot;
vector<pair<int,int> > Q[Maxn];
int vis[Maxn][Maxn],fa[Maxn];
int inst[Maxn],dis[Maxn],dep[Maxn];
priority_queue<Edge> st;
int deal(int s,int n) {
	memset(dis,0x3f3f3f3f,sizeof(dis));
	memset(vis,0,sizeof(vis));
	memset(inst,0,sizeof(inst));
	fa[s] = dis[s] = 0;
	st.push({s,0,0});
	while(!st.empty()) {
		int x = st.top().u;
		st.pop();
		if(inst[x])continue;
		inst[x] = 1;
		for(auto u:Q[x])
			if(dis[u.first] > dis[x]+u.second)
				dis[u.first] = dis[x]+u.second,
				fa[u.first] = x,dep[u.first] = dep[x]+1,
				st.push({u.first,x,dis[u.first]});
	} 
	for(int i=1;i<=n;i++)
		vis[i][fa[i]] = vis[fa[i]][i] = 1;
	int ans = INT_MAX;
	for(int i=1;i<=tot;i++) {
		int lc = e[i].u,rc = e[i].v;
		if(vis[lc][rc])continue;
		while(lc != rc) {
			if(dep[lc] > dep[rc])
				swap(lc,rc);
			rc = fa[rc];
		} if(lc != s)continue;
		ans = min(ans,dis[e[i].u]+dis[e[i].v]+e[i].w);
	} return ans == INT_MAX?-1:ans;
}
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int sub,n;
	cin>>sub>>n;
	for(int i=1;i<n;i++) {
		for(int j=i+1;j<=n;j++) {
			int x; cin>>x;
			if(x != -1)e[++tot] = {i,j,x},
			Q[i].push_back({j,x}),
			Q[j].push_back({i,x});
		}
	}
	for(int i=1;i<=n;i++)
		cout<<deal(i,n)<<" ";
	return 0;
}