rt

思路是先每个点通过Dijkstra跑一遍，ans记上答案，如果是以s为初始的结点，ans就从$2$到$n$跑一遍加上答案。不知道是代码有问题还是思路错了QAQ

#include <bits/stdc++.h>
#define maxn 5000100
//关于_ _ _ _，它死了
using namespace std;
const int inf = 2147483647;
int n, m, s, cnt;
int dis[maxn]; //深进是对结构体有怨念吗......

int h[maxn];
int to[maxn];
int val[maxn];
int nxt[maxn];
bool vis[maxn];

struct node {
	int v, w;
	friend bool operator < (node a, node b) {
		return a.w > b.w;
	}
} tmp;
priority_queue<node> q;


void add(int a, int b, int c) {
	to[++cnt] = b;
	val[cnt] = c;
	nxt[cnt] = h[a];
	h[a] = cnt;
}
int ans = 0;

void dijkstra() {
	while (!q.empty()) {
		q.pop();
	}
	for (int i = 1; i <= n; i++) {
		dis[i] = inf;
	}
	dis[s] = 0;
	tmp.v = s;
	tmp.w = 0;
	q.push(tmp);
	while (!q.empty()) {
		int u = q.top().v;
		q.pop();
		if (vis[u]) {
			continue;
		}
		vis[u] = 1;
		for (int i = h[u]; i; i = nxt[i]) {
			if (dis[to[i]] > (long long)dis[u] + val[i]) { //处理溢出问题
				dis[to[i]] = dis[u] + val[i];
				tmp.w = dis[to[i]];
				tmp.v = to[i];
				q.push(tmp);
			}
		}
	}
}

int main() {
	cin >> n >> m;
	for (int i = 1, u, v, w; i <= m; i++) {
		cin >> u >> v >> w;
		add(u, v, w);
	}
	for (int i = 1; i <= n; i++) {
		s = i;
		dijkstra();
		if (i == 1) {
			for (int j = 2; j <= n; j++) {
				ans += dis[j];
			}
		} else {
			ans += dis[1];
		}
	}
	cout << ans;
	return 0;
}