可以进行反向建边+SPFA

记得开long long， 并跑两遍SPFA，代码极短（求关）

上代码:

#include <bits/stdc++.h>
using namespace std;
long long dis[1000005], n, m, ans, u[1000005], v[1000005], w[1000005];
bool vis[1000005];
vector<pair<int, int> > g[1000005];
void bfs(long long x) {
	memset(dis, 0x3f, sizeof(dis));
	memset(vis, false, sizeof(vis));
	queue<int> q;
	q.push(x);
	dis[x] = 0;
	vis[x] = true;
	while(q.size()) {
		int x = q.front();
		q.pop();
		vis[x] = false;
		for(int i = 0; i < g[x].size(); i ++) {
			long long v = g[x][i].first, w = g[x][i].second;
			if(dis[v] > dis[x] + w) {
				dis[v] = dis[x] + w;
				if(!vis[v]) {
					vis[v] = true;
					q.push(v);
				}
			}
		}
	}
}
int main() {
	cin >> n >> m;
	for(long long i = 1; i <= m; i ++) {
		cin >> u[i] >> v[i] >> w[i];
		g[u[i]].push_back({v[i], w[i]});
	}
	bfs(1);
	for(long long i = 1; i <= n; i ++) ans += dis[i], g[i].clear();
	for(long long i = 1; i <= m; i ++) g[v[i]].push_back({u[i], w[i]});
	bfs(1);
	for(long long i = 1; i <= n; i ++) ans += dis[i];
	cout << ans;
	return 0;
}