信息：

样例过。

第一个测试点输出 2494。

#include<bits/stdc++.h>
using namespace std;
struct node{
	int u,v,w,nxt;
}e1[100005],e2[100005];
priority_queue<pair<int,int> >q1,q2;
int n,m,head1[1005],head2[1005],cnt1,a[1005][1005],cnt2,dis1[1005],dis2[1005],vis1[1005],vis2[1005];
void add1(int u,int v,int w){
	e1[++cnt1].u=u;
	e1[cnt1].v=v;
	e1[cnt1].w=w;
	e1[cnt1].nxt=head1[u];
	head1[u]=cnt1;
}
void add2(int u,int v,int w){
	e2[++cnt2].u=u;
	e2[cnt2].v=v;
	e2[cnt2].w=w;
	e2[cnt2].nxt=head2[u];
	head2[u]=cnt2;
}
void dj1(){
	pair<int,int>t;
	t.first=0;
	t.second=1;
	q1.push(t);
	while(!q1.empty()){
		t=q1.top();q1.pop();
		int t1=t.first,t2=t.second;
		if(vis1[t2])continue;
		vis1[t2]=1;
		for(int i=head1[t2];i;i=e1[i].nxt){
			if(dis1[e1[i].v]>e1[i].w+t1){
				dis1[e1[i].v]=e1[i].w+t1;
				if(!vis1[e1[i].v])q1.push({dis1[e1[i].v],e1[i].v});
			}
		}
	}
}
void dj2(){
	pair<int,int>t;
	t.first=0;
	t.second=1;
	q2.push(t);
	while(!q2.empty()){
		t=q2.top();q2.pop();
		int t1=t.first,t2=t.second;
		if(vis2[t2])continue;
		vis2[t2]=2;
		for(int i=head2[t2];i;i=e2[i].nxt){
			if(dis2[e2[i].v]>e2[i].w+t1){
				dis2[e2[i].v]=e2[i].w+t1;
				if(!vis2[e2[i].v])q2.push({dis2[e2[i].v],e2[i].v});
			}
		}
	}
}
long long ans=0;
int main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		dis1[i]=2147483647;
		dis2[i]=2147483647;
		for(int j=1;j<=n;j++)a[i][j]=2147483647;
	}
	for(int i=1;i<=m;i++){
		int u,v,w;
		cin>>u>>v>>w;
		if(a[u][v]<w)continue;
		add1(u,v,w);
		add2(v,u,w);
	}
	dj1();dj2();
	for(int i=2;i<=n;i++){
		ans+=dis1[i];
		ans+=dis2[i];
	}
	cout<<ans;
	return 0;
}