// luogu-judger-enable-o2
// C++11
#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4.1,sse4.2,avx,avx2,popcnt,tune=native")
#include <immintrin.h>
#include <emmintrin.h>
#include <bits/stdc++.h>
#define ri register int
using namespace std;
inline int read(){
    int x=0,f=1;char ch=getchar();
    while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
    while(isdigit(ch)){x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}
    return x*f;
}
int n,m,dis[1005][1005];
int main(){
    memset(dis,0x3f,sizeof(dis));
    n=read();m=read();
    for(ri i=1,x,y,z;i<=m;++i){
        x=read();y=read();z=read();
        dis[x][y]=min(dis[x][y],z);
    }
    for(ri k=1;k<=n;++k)
        for(ri i=1;i<=n;++i)
            for(ri j=1;j<=n;++j)
                dis[i][j]=min(dis[i][k]+dis[k][j],dis[i][j]);
    int ans=0;
    for(ri i=2;i<=n;++i)
        ans+=(dis[i][1]+dis[1][i]);
    printf("%d\n",ans);
    return 0;
}