#include<bits/stdc++.h>
#define MOD 100003
#define INF 0x3f3f3f3f
using namespace std;
const int maxn=2000005;
int n,m,s=1;
int idx=1,e[maxn],w[maxn],head[maxn],ne[maxn];
int dis[maxn],vis[maxn];
int ans;
struct Node
{
	int dis,x;
	bool operator<(Node p)const{return dis>p.dis;}
	Node(int dis,int x):dis(dis),x(x){}
};

inline int read()
{
	int date=0,w=1;
	char c;
	c=getchar();
	while(c<'0' || c>'9')
	{
		if(c=='-')w=-1;
		c=getchar();
	}
	while(c>='0' && c<='9')
	{
		date=date*10+(c-'0');
		c=getchar();
	}
	return date*w;
}

void add(int a,int b,int c)
{
	e[idx]=b;
	w[idx]=c;
	ne[idx]=head[a];
	head[a]=idx++; 
}

void dijkstra()
{
	memset(dis,INF,sizeof(dis));
	priority_queue<Node>q;
	dis[s]=0;
	Node u(dis[s],s);
	q.push(u);
	while(!q.empty())
	{
		Node u=q.top();
		q.pop();
		if(vis[u.x])continue;
		vis[u.x]=1;
		for(int i=head[u.x];i!=-1;i=ne[i])
		{
			if(dis[e[i]]>dis[u.x]+w[i])
			{
				dis[e[i]]=dis[u.x]+w[i];
				Node v(dis[e[i]],e[i]);
				q.push(v);
			}
		}
	}
	while(!q.empty())q.pop();
}
signed main()
{
	memset(head,-1,sizeof(head));
	n=read(),m=read();
	for(int i=1;i<=m;i++)
	{
		int a=read(),b=read(),c=read();
		add(a,b,c);
		add(a+n,b+n,c);
	}
	dijkstra();
	for(int i=2;i<=n;i++)ans+=dis[i];
	s+=n;
	dijkstra();
	for(int i=2+n;i<=2*n;i++)ans+=dis[i];
	cout<<ans;
	return 0;
}

题目