#include<bits/stdc++.h>
#define MAXN 20000
using namespace std;
struct edge{
	int to,next,dis;
};
edge e[MAXN];
int n,m;
unsigned long long ans=0;
int dis[MAXN<<1],vis[MAXN<<1],head[MAXN<<1],cnt;
struct node{
	int dis;
	int pos;
	bool operator<(const node &x)const{
	    return x.dis<dis;
	}
};
priority_queue<node> q;
inline void add_edge(int u,int v,int dis){
	e[++cnt].dis=dis;
	e[cnt].next=head[u];
	e[cnt].to=v;
	head[u]=cnt;
}
void dij(int s){
	dis[s]=0;
	q.push((node){0,s});
	while(!q.empty()){
		node tmp=q.top();
		q.pop();
		int x=tmp.pos,d=tmp.dis;
		if(vis[x]) continue;
		vis[x]=true;
		for(int i=head[x];i;i=e[i].next){
			int y=e[i].to;
			if(dis[y]>dis[x]+e[i].dis){
				dis[y] = dis[x] + e[i].dis;
				if(!vis[y]) q.push((node){dis[y],y});
			}
		}
	}
}
int main(){
	freopen("ceshi.in","r",stdin);
	freopen("ceshi.out","w",stdout);
	cin>>n>>m;
	for(int i=1;i<=n<<1;++i) dis[i]=0x7fffff;
	for(int i=1;i<=m;++i){
		int u,v,d;
		cin>>u>>v>>d;
		add_edge(u,v,d);
		add_edge(v+n,u+n,d);
	}
	dij(1);
	for(int i=2;i<=n;++i) ans+=dis[i];
	dij(1+n);
	for(int i=2+n;i<=n*2;++i) ans+=dis[i];
	cout<<ans;
	fclose(stdin);
	fclose(stdout);
	return 0;
}

我无语了…………

n*2是为了反图 求大佬帮一下