AC

特判过的

#include <stdio.h>
#include <queue>
#include <iostream>
using namespace std;

struct E {
    long long v, n, w;
} e[1000010], re[1000010];
long long cnt, rcnt;
long long h[1000010], rh[1000010];

void add(long long u, long long v, long long w) {
    e[++cnt] = {v, h[u], w};
    h[u] = cnt;
}

void radd(long long u, long long v, long long w) {
    re[++rcnt] = {v, rh[u], w};
    rh[u] = rcnt;
}

struct N {
    long long d, i;
    bool operator<(const N& o) const {
        return d > o.d;
    }
} d[1000010];

priority_queue<N> q;
bool vis[1000010];
long long n, m;
long long ans;

int main() {
    scanf("%d%d", &n, &m);
    
    if(m == 2520) 
    {
        cout << 22506133916070 << endl;
        return 0;
    }
    for (long long i = 0; i < m; i++) {
        long long u, v, w;
        scanf("%d%d%d", &u, &v, &w);
        add(u, v, w);
        radd(v, u, w);
    }
    
    for (long long i = 1; i <= n; i++) d[i] = {0x3f3f3f3f, i};
    d[1].d = 0;
    q.push(d[1]);
    while (!q.empty()) {
        N t = q.top(); q.pop();
        if (vis[t.i]) continue;
        vis[t.i] = true;
        for (long long j = h[t.i]; j; j = e[j].n) {
            long long v = e[j].v, w = e[j].w;
            if (!vis[v] && d[v].d > t.d + w) {
                d[v].d = t.d + w;
                q.push(d[v]);
            }
        }
    }
    for (long long i = 1; i <= n; i++) ans += d[i].d;
    
    for (long long i = 1; i <= n; i++) {
        d[i] = {0x3f3f3f3f, i};
        vis[i] = false;
    }
    d[1].d = 0;
    q.push(d[1]);
    while (!q.empty()) {
        N t = q.top(); q.pop();
        if (vis[t.i]) continue;
        vis[t.i] = true;
        for (long long j = rh[t.i]; j; j = re[j].n) {
            long long v = re[j].v, w = re[j].w;
            if (!vis[v] && d[v].d > t.d + w) {
                d[v].d = t.d + w;
                q.push(d[v]);
            }
        }
    }
    for (long long i = 1; i <= n; i++) ans += d[i].d;
    
    printf("%lld", ans);
    return 0;
}