#include <bits/stdc++.h>
#define int long long
#define INF 1E8
using namespace std;

int e[1005][1005],x,y,t,n,cnt,m;
void init(){
    for(int i=1;i<=1000;i++){
        for(int j=1;j<=1000;j++){
            if(i!=j) e[i][j]=INF;
            else e[i][j]=0;
        }
    }
}
signed main(){
    init();
    cin>>n>>m;
    for(int i=1;i<=m;i++){
        cin>>x>>y>>t;
        e[x][y]=min(e[x][y],t);
    }
    for(int k=1; k<=n; k++) {
        for(int i=1; i<=n; i++) {
            for(int j=1; j<=n; j++) {
                if(e[i][j]>e[i][k]+e[k][j])
                    e[i][j]=e[i][k]+e[k][j];
            }
        }
    }
    for(int i=2;i<=n;i++){
        cnt+=e[1][i];
        cnt+=e[i][1];
    }
    cout<<cnt;
    return 0;
}