$\text{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;
}