#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <queue>
using namespace std;

int n, m;
struct Node { int u, t; };
vector<vector<int> > adj;
vector<vector<int> > adj2;
vector<int> vis;
vector<int> ans;
queue<Node> q;
int main() {
    cin >> n >> m;
    adj.resize(n + 1, vector<int>(n + 1, 1e9));
    adj2.resize(n + 1, vector<int>(n + 1, 1e9));
    vis.resize(n + 1, false);
    ans.resize(n + 1, 0);
    
    int u, v, t;
    for (int i = 1; i <= m; i++) {
        cin >> u >> v >> t;
        adj[u][v] = min(adj[u][v], t);
        adj2[v][u] = min(adj2[v][u], t);
    }
    
    q.push({1, 0});
    vis[1] = true;
    while (!q.empty()) {
        Node node = q.front(); q.pop();
        ans[node.u] += node.t;
        for (int i = 1; i <= n; i++)
            if (adj[node.u][i] != (int)1e9 && !vis[i])
                vis[i] = true, q.push({i, node.t + adj[node.u][i]});
    }
    
    vis.assign(n + 1, false);
    q.push({1, 0});
    vis[1] = true;
    while (!q.empty()) {
        Node node = q.front(); q.pop();
        ans[node.u] += node.t;
        for (int i = 1; i <= n; i++)
            if (adj2[node.u][i] != (int)1e9 && !vis[i])
                vis[i] = true, q.push({i, node.t + adj2[node.u][i]});
    }
    
    int sum = 0;
    for (int i = 2; i <= n; i++) sum += ans[i];
    cout << sum << endl;
    return 0;
}