#include<bits/stdc++.h>
using namespace std;
const int maxn=2005;
int n,m;
int e[maxn][maxn];
int dis[maxn],vis[maxn];
void f(int n,int s,int off){
for(int i=0;i<=2*n;i++) dis[i] = 1e9;
dis[s] = 0;
for(int i = 1;i<=n;i++){
int u = 0;
for(int j=1+off;j<=n+off;j++){
if(!vis[j] && dis[j]<dis[u]) u=j;
}
vis[u]=1;
for(int j=1+off;j<=n+off;j++){
if(e[u][j]){
int v=j;
int w=e[u][j];
if(dis[v]>dis[u]+w){
dis[v]=dis[u]+w;
}
}
}
}
}
int main(){
cin>>n>>m;
for(int i=0;i<m;i++){
int u,v,w;
cin>>u>>v>>w;
int tmp=e[u][v] ? e[u][v]:1e9;
e[u][v] = min(tmp,w);
e[v+n][u+n] = min(tmp,w);
}
f(n,1,0);
int ans=0;
for(int i=2;i<=n;i++){
ans+=dis[i];
}
f(n,n+1,n);
for(int i=2+n;i<=n+n;i++){
ans+=dis[i];
}
cout<<ans;
return 0;
}