O(2)+火车头
#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<algorithm>
#include<cstdio>
using namespace std;
inline int read()
{
int s=0,w=1;
char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
while(ch>='0'&&ch<='9')s=s*10+(ch-'0'),ch=getchar();
return s*w;
}
const int MAXN=1010;
int dp[MAXN][MAXN],ans,n,m;
int main()
{
n=read(),m=read();
for(register int i=1;i<=n;i++)for(register int j=1;j<=n;j++)dp[i][j]=1e9;
while(m--)
{
int u,v,w;
u=read(),v=read(),w=read();
dp[u][v]=min(dp[u][v],w);
}
for(register int k=1;k<=n;k++)for(register int i=1;i<=n;i++)for(register int j=1;j<=n;j++)dp[i][j]=min(dp[i][j],dp[i][k]+dp[k][j]);
for(int i=2;i<=n;i++)ans+=(dp[1][i]+dp[i][1]);
printf("%d\n",ans);
return 0;
}