我们希望1到X和X到1都是最短路，有个难点是多个起点到终点的最短路，就要用到反向建边，反向建一个图，然后跑1到x的最短路，得到的结果就是x到1的最短路，因为这条路径是反着的，我们扭回来就正好是x到1了。

在形式上不要写的像我一样，可以用vector模拟静态邻接链表。

时间复杂度O(mlogn)

#include <iostream>
#include <queue>
#include <algorithm>
#include <string.h>
using namespace std;
typedef long long ll;
#define IOS ios::sync_with_stdio(false),cin.tie(0);
#define endl cout<<"\n";
const int N = 1e3 + 7;
const int M = 1e5 + 7;
struct node {
    int to, next, c;
} e1[M], e2[M];
int h1[N], h2[N];
int cnt1, cnt2;
void add1(int x, int y, int z) {
    e1[++cnt1].c = z;
    e1[cnt1].to = y;
    e1[cnt1].next = h1[x];
    h1[x] = cnt1;
    return;
}

void add2(int x, int y, int z) {
    e2[++cnt2].c = z;
    e2[cnt2].to = y;
    e2[cnt2].next = h2[x];
    h2[x] = cnt2;
    return;
}

int n, m;
int d1[N];
int d2[N];
int vis[N];
priority_queue<pair<int, int>> q;
void dij(int s, int flag) {
    memset(vis, 0, sizeof vis);
    while (q.size())q.pop();
    int* dist = flag == 0 ? d1 : d2;
    dist[s] = 0;
    q.push({0, s});
    while (!q.empty()) {
        int x = q.top().second;
        q.pop();
        if (vis[x])continue;
        vis[x] = 1;
        //cout<<"pok\n";
        int* h = flag == 0 ? h1 : h2;
        node* e = flag == 0 ? e1 : e2;
        for (int i = h[x]; i; i = e[i].next) {
            int v = e[i].to;
            if (dist[v] >= dist[x] + e[i].c) {
                dist[v] = dist[x] + e[i].c;
                q.push({-1 * dist[v], v});
            }
        }
    }
    return;
}
void solve() {
    cin >> n >> m;
    for (int i = 1; i <= m; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        add1(a, b, c); //正向建边
        add2(b, a, c); //反向建边
    }
    memset(d1, 0x3f3f3f3f, sizeof d1);
    memset(d2, 0x3f3f3f3f, sizeof d2);
    dij(1, 0);
    dij(1, 1);
    int ans = 0;
    for (int i = 2; i <= n; i++) {
        ans += d1[i] + d2[i];
    }
    cout << ans;
}
int main() {
    //IOS;
    int T = 1;
    //cin>>T;
    while (T--)solve();
    return 0;
}