代码↓

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define P pair<ll,ll>
#define w first
#define s second
const int N=5e5+5;
ll dis[N];
ll g[2001][2001];
ll g2[2001][2001];
bool vis[N];
ll n,m;
inline ll read()
{
	ll ans=0,f=1;
	char x=getchar();
	while(x<'0' || x>'9')
	{
		if(x=='-') f=-1;
		x=getchar();
	}
	while(x>='0' && x<='9')
	{
		ans=(ans<<3)+(ans<<1)+x-'0';
		x=getchar();
	}
	return ans*f;
}
void ds(ll x)
{
	memset(dis,0x3f,sizeof(dis));
	memset(vis,0,sizeof(vis));
	priority_queue<P,vector<P>,greater<P> > q;
	dis[x]=0;
	q.push({0,x});
	while(q.size())
	{
		P cur=q.top();
		q.pop();
		if(vis[cur.s]) continue;
		vis[cur.s]=1;
		for(int i=1;i<=n;i++)
		{
			if(g[cur.s][i]!=0x3f)
			{
				if(dis[i]>g[cur.s][i]+cur.w)
				{
					dis[i]=g[cur.s][i]+cur.w;
					q.push({dis[i],i});
				}
			}
		}
	}
}
void ds2(ll x)
{
	memset(dis,0x3f,sizeof(dis));
	memset(vis,0,sizeof(vis));
	priority_queue<P,vector<P>,greater<P> > q;
	dis[x]=0;
	q.push({0,x});
	while(q.size())
	{
		P cur=q.top();
		q.pop();
		if(vis[cur.s]) continue;
		vis[cur.s]=1;
		for(int i=1;i<=n;i++)
		{
			if(g2[cur.s][i]!=0x3f)
			{
				if(dis[i]>g2[cur.s][i]+cur.w)
				{
					dis[i]=g2[cur.s][i]+cur.w;
					q.push({dis[i],i});
				}
			}
		}
	}
}
int main()
{
	memset(g,0x3f,sizeof(g));
	memset(g2,0x3f,sizeof(g2));
	n=read();
	m=read();
	for(int i=1;i<=m;i++)
	{
		ll u,v,w;
		u=read();
		v=read();
		w=read();
		g[u][v]=w;
		g2[v][u]=w;
	}
	ll ans=0;
	ds(1);
	for(int i=2;i<=n;i++) ans+=dis[i];
	ds2(1);
	for(int i=2;i<=n;i++) ans+=dis[i];
	printf("%d\n",ans);
	return 0;
}