dijkstra貌似要一种松弛操作，这需要一个二维数组$s$，可这样就超空间了呀！如何避免这种问题？

松弛操作如下：

设 $dis[i]$ 为起点至 $i$ 点的最短路， $s[i][j]$ 为 $i$ 点到 $j$ 点的最短路，则松弛操作为：

$dis[i] = min(dis[i],dis[j] + s[j][i])$

CODE:

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int inf = 0x3f3f3f3f;
const int M = 5005;
const int start = 1;
int u[M];
int v[M];
int w[M];
int s[M][M];
int dis[M];
bool vis[M];
signed main() {
	int n,m,sum = 0;
	cin >> n >> m;
	for (int i = 1; i <= m; i++) {
		cin >> u[i] >> v[i] >> w[i];
	}
	for (int x = 1; x <= 2; x++) {
		memset(s,inf,sizeof s);
		for (int i = 1; i <= n; i++) s[i][i] = 0;
		for (int i = 1; i <= m; i++) {
			s[u[i]][v[i]] = min(s[u[i]][v[i]],w[i]);
		}
		for (int i = 1; i <= n; i++) dis[i] = s[start][i];
		memset(vis,false,sizeof vis);
		vis[1] = true;
		for (int i = 1; i < n; i++) {
			int mnid = -1,mnn = inf;
			for (int j = 1; j <= n; j++) {
				if (!vis[j] && dis[j] < mnn) {
					mnn = dis[j];
					mnid = j;
				}
			}
			vis[mnid] = true;
			for (int j = 1; j <= n; j++) {
				dis[j] = min(dis[j],dis[mnid] + s[mnid][j]);
			}
		}
		for (int i = 1; i <= m; i++) {
			swap(u[i],v[i]);
		}
		for (int i = 1; i <= n; i++) sum += dis[i];
	}
	cout << sum;
	return 0;
}