P1629来的，pts25

#include<bits/stdc++.h>
using namespace std;
const long long INF = 2e18;
long long n, m;
long long u[100005], v[100005], w[100005];
long long dis[100005];
void f(){
    for(long long i = 1; i <= n; i ++) dis[i] = INF;
    dis[1] = 0;
    for(long long k = 1; k <= n - 1; k ++)
        for(long long i = 1; i <= m; i ++)
            if(dis[v[i]] > dis[u[i]] + w[i])
                dis[v[i]] = dis[u[i]] + w[i];
}
int main(){
    scanf("%lld%lld", &n, &m);
    for(long long i = 1; i <= m; i ++) scanf("%lld%lld%lld", &u[i], &v[i], &w[i]);
    long long ans = 0;
    f();
    for(long long i = 1; i <= n; i ++) ans += dis[i];
    for(long long i = 1; i <= m; i ++) swap(u[i], v[i]);
    f();
    for(long long i = 1; i <= n; i ++) ans += dis[i];
    printf("%lld", ans);
    return 0;
}