#include<bits/stdc++.h>
#include<unordered_map>
using namespace std;
typedef int ll;
const ll  N = 6000, M = 1e6;
typedef pair<ll, ll >PII;
ll  n, m, t;
ll  head[N], e[M], en[M], idx = 0, w[M];
int dist[N];
priority_queue<PII>q;
int res = 0;
void add(ll  a, ll  b, ll  c)
{
    e[idx] = b, w[idx] = c, en[idx] = head[a], head[a] = idx++;
}
void   cal(ll  x)
{
    memset(dist, 0x3f, sizeof dist);
    dist[x] = 0;
    q.push({ 0,x });
    while (q.size())
    {
        auto t = q.top();
        q.pop();
        ll  ver = t.second;
        ll  distance = t.first;
        for (ll i = head[ver]; ~i; i = en[i])
        {
            ll  j = e[i];
            if (dist[j] > distance + w[i])
            {
                dist[j] = distance + w[i];
                q.push({ dist[j],j });
            }
        }
    }
}
int main()
{
    memset(head, -1, sizeof head);
       scanf("%d %d", &n, &m);
    for (ll i = 1; i <= m; i++)
    {
        ll  a, b, c;
       scanf("%d %d %d", &a, &b, &c);
        add(a, b, c);
        add(b + n, a + n, c);
    }
    ll ans = 0;
    cal(1);
    for (ll i = 2; i <= n; i++) ans += dist[i];
    cal(1 + n);
    for (ll i = 2 + n; i <= n + n; i++)  ans += dist[i];
    cout << ans << endl;
    return 0;
}