POJ - 1511

#include<cstdio>
#include<algorithm>
#include<queue>
#include<cstring>
using namespace std;
typedef pair<long long,long long> PII;
const long long maxn=1000005;
long long n,m;
struct node{
	long long _this,next,w;
	node(){
		_this=next=w=0;
	}
}To[maxn<<1],Come[maxn<<1];
long long headnextTo[maxn],headnextCome[maxn];
long long idxTo,idxCome;
void merge(long long from,long long to,long long w,long long T){
	if(T==0){
		To[++idxTo]._this=to;
		To[idxTo].w=w;
		To[idxTo].next=headnextTo[from];
		headnextTo[from]=idxTo;
	}
	else{
		Come[++idxCome]._this=to;
		Come[idxCome].w=w;
		Come[idxCome].next=headnextCome[from];
		headnextCome[from]=idxCome;
	}
}
long long dis[maxn];
bool vis[maxn];
long long ans;
priority_queue<PII,vector<PII>,greater<PII> > heap;
long long dij(long long from){
	while(!heap.empty()) heap.pop();
	memset(dis,0x3f3f3f3f,sizeof dis);
	memset(vis,0,sizeof vis);
	dis[from]=0;
	heap.push(make_pair(0,from));
	while(heap.size()){
		long long nowid=heap.top().second;
		long long nowdis=heap.top().first;
		heap.pop();
		if(vis[nowid]) continue;
		vis[nowid]=1;
		for(long long i=headnextTo[nowid];i!=0;i=To[i].next){
			long long _try=To[i]._this;
			if(dis[_try]>nowdis+To[i].w){
				dis[_try]=nowdis+To[i].w;
				heap.push(make_pair(dis[_try],_try));
			}
		}
	}
	for(long long i=2;i<=n;++i){
		ans+=dis[i];
	}
	
	
	while(!heap.empty()) heap.pop();
	memset(dis,0x3f3f3f3f,sizeof dis);
	memset(vis,0,sizeof vis);
	dis[from]=0;
	heap.push(make_pair(0,from));
	while(heap.size()){
		long long nowid=heap.top().second;
		long long nowdis=heap.top().first;
		heap.pop();
		if(vis[nowid]) continue;
		vis[nowid]=1;
		for(long long i=headnextCome[nowid];i!=0;i=Come[i].next){
			long long _try=Come[i]._this;
			if(dis[_try]>nowdis+Come[i].w){
				dis[_try]=nowdis+Come[i].w;
				heap.push(make_pair(dis[_try],_try));
			}
		}
	}
	for(long long i=2;i<=n;++i){
		ans+=dis[i];
	}
	return ans;
}
int main(){
	long long _;
	scanf("%lld",&_);
	while(_--){
		memset(headnextTo,0,sizeof headnextTo);
		memset(headnextCome,0,sizeof headnextCome);
		idxTo=idxCome=ans=0;
		scanf("%lld%lld",&n,&m);
		for(long long i=1;i<=m;++i){
			long long s,t,w;
			scanf("%lld%lld%lld",&s,&t,&w);
			merge(s,t,w,0);
			merge(t,s,w,1);
		}
		printf("%lld\n",dij(1));
	}
	return 0;
}