这题

代码：

#include<vector>
#include<cstdio>
#include<queue>
using namespace std;
typedef long long ll;

const int N = 1e5 + 10;
const ll inf = 1e10;

struct Edge {
	int v;
	ll w;
};

struct Node { 
	int u;
	ll dis;
	bool operator < (const Node &n) const {
		return dis > n.dis;
	}
};

int n, m, ans;
vector<Edge> G[N];
bool vis[N];
ll dis[N],diss[N];

void Dijkstra(int s) {
	priority_queue<Node> Q;
	for (int i = 1; i <= n; i++) {
		vis[i] = false;
		dis[i] = inf;
	}
	dis[s] = 0;
	Q.push((Node) {
		s, dis[s]
	});
	while (!Q.empty()) {
		Node node = Q.top();
		Q.pop();
		int u = node.u;
		int d = node.dis;
		if (vis[u]) continue;
		vis[u] = true;
		for (int j = 0 ; j < (int)G[u].size(); j++) {
			int v = G[u][j].v;
			int w = G[u][j].w;
			if (dis[v] > d + w) {
				dis[v] = d + w;
				Q.push((Node) {
					v, dis[v]
				});
			}
		}
	}
}

int main() {
	scanf("%d%d", &n, &m); 
	while (m--) {
		int u, v;
		ll w;
		scanf("%d%d%lld", &u, &v, &w);
		G[u].push_back((Edge) {
			v, w
		});
	}
	for (int i = 1; i <= n; i++)  {
		Dijkstra(i);
		diss[i]=dis[1];
	}
	Dijkstra(1);
	for(int i=1; i<=n; ++i)
		ans+=diss[i]+dis[i];
	printf("%d\n",ans);
}