#include<bits/stdc++.h>
using namespace std;
#define int long long
struct E{
    int v,w;
};
struct node{
    int dis,id;
};
vector<E> e[100005];
int n,m,ans,dis[100005];
bool vis[100005];
bool operator <(const node &x,const node &y){
    return y.dis<x.dis;
}
priority_queue<node> q;
void Dijkstra(int s){
    fill(dis,dis+1+n,INT_MAX);
    dis[s]=0;
    q.push((node){0,s});
    while(!q.empty())
    {
        node tmp=q.top();
        q.pop();
        int u=tmp.id;
        if(tmp.dis>dis[u]) continue;
        for(auto v:e[u])
            if(dis[v.v]>dis[u]+v.w) dis[v.v]=dis[u]+v.w,q.push((node){dis[v.v],v.v});
    }
}
signed main(){
    ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    cin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        int u,v,w;
        cin>>u>>v>>w;
        e[u].push_back({v,w}),e[v+n].push_back({u+n,w});
    }
    Dijkstra(1);
    for(int i=2;i<=n;i++)
        ans+=dis[i];
    Dijkstra(1+n);
    for(int i=2+n;i<=(n<<1);i++)
        ans+=dis[i];
    cout<<ans;
    return 0;
}