，inf 0x7FFFFFF wa， 7 F ， ！！if(w+d[t]<d[temp]) ！！
spfa
#include<iostream>
using namespace std;
#include<queue>
#include<algorithm>
#include<memory.h>
#define N 1000005
#define inf 0x7FFFFFFF
struct node
{
int u;
int c;
int next;
}e[N],o[N];
int a[N],b[N],c[N],p[N];
long long d[N];
bool vis[N];
int te=0;
void add(int a,int b,int c)
{
e[te].u=a;
e[te].c=c;
e[te].next=p[b];
p[b]=te;
te++;
}
int spfa(int s)
{
d[s]=0;
vis[s]=true;
queue<int>q;
q.push(s);
while(!q.empty())
{
int t=q.front();
q.pop();
vis[t]=false;
for(int j=p[t];j!=-1;j=e[j].next)
{
int w=e[j].c;
int temp=e[j].u;
if(w+d[t]<d[temp])
{
d[temp]=w+d[t];
if(!vis[temp])
{
vis[temp]=true;
q.push(temp);
}
}
}
}
}
int main()
{
int n,q;
int sum;
while(cin>>n)
{
while(n--)
{
scanf("%d%d",&sum,&q);
for(int i=0;i<N;i++)
{
p[i]=-1;
}
memset(vis,0,sizeof(vis));
fill(d,d+N,inf);
te=0;
for(int i=1;i<=q;i++)
{
scanf("%d%d%d",&a[i],&b[i],&c[i]);
add(a[i],b[i],c[i]);
}
spfa(1);
long long sum1=0;
for(int i=1;i<=sum;i++)
sum1+=d[i];
memset(vis,0,sizeof(vis));
for(int i=0;i<N;i++)
d[i]=inf;
for(int i=0;i<N;i++)
{
p[i]=-1;
}
te=0;
for(int i=1;i<=q;i++)
{
add(b[i],a[i],c[i]);
}
spfa(1) ;
long long sum2=0;
for(int i=1;i<=sum;i++)
sum2+=d[i];
cout<<sum1+sum2<<endl;
}
}
return 0;
}