#include <iostream>
#include <queue>
#include <cstdio>
#include <cstring>
#define int long long
using namespace std;
int n,m,ans,cnt;
int u, v, w;
int dis[2010], head[2010];
bool vis[2010];
struct edge
{
    int to, next, dis;
}a[200010];
struct node
{
    int dis, pos;
    friend bool operator < (node a, node b) {
        return a.dis < b.dis;
    }
};
void add(int u, int v, int w)
{
    a[++ cnt].dis = w;
    a[cnt].to = v;
    a[cnt].next = head[u];
    head[u] = cnt;
}
priority_queue<node> q;
void dijkstra(int s)
{
    memset(vis, 0, sizeof(vis));
    for (int i = 1;i <= 2 * n;i ++) dis[i] = 0x7ffffffff;
    dis[s] = 0;
    q.push({0, s});
    while (!q.empty())
    {
        node temp = q.top();
        q.pop();
        int x = temp.pos;
        if (vis[x]) continue;
        vis[x] = 1;
        for (int i = head[x];i;i = a[i].next)
        {   
            int y = a[i].to;
            if (dis[y] > dis[x] + a[i].dis)
            {
                dis[y] = dis[x] + a[i].dis;
                if (!vis[y]) q.push({dis[y], y});
            }
        }
    }
}
signed main()
{
    scanf("%lld %lld", &n, &m);
    for (int i = 1;i <= m;i ++)
    {
        scanf("%lld %lld %lld", &u, &v, &w);
        add(u, v, w);
        add(v + n, u + n, w);
    }
    dijkstra(1);
    for (int i = 1;i <= n;i ++) ans += dis[i];
    dijkstra(1 + n);
    for (int i = 1 + n;i <= 2 * n;i ++) ans += dis[i];
    printf("%lld\n", ans);
    return 0;
}