```c++
#include
#include
#include
#include
#include
using namespace std;
const int maxn=1e6+1;
const int inf=0x3f3f3f3f;
int head[2][maxn],vis[2][maxn];
int dis[2][maxn];
int n,m,s,cnt=1;
struct Node{
int to;
int w;
int next;
}edge[2][maxn];
void add(int f,int u,int v,int w){
edge[f][cnt].to=v;
edge[f][cnt].w=w;
edge[f][cnt].next=head[f][u];
head[f][u]=cnt++;
}
struct node{
int to;
int w;
bool operator<(const node &x)const
{
return x.wvoid dijkstra(int f,int s){
priority_queuequ;
dis[f][s]=0;
qu.push((node){s,0});
while(!qu.empty()){
node temp=qu.top();
qu.pop();
int x=temp.to,y=temp.w;
if(vis[f][x]){
continue;
}
vis[f][x]=1;
for(int i=head[f][x];i!=0;i=edge[f][i].next) {
int t=edge[f][i].to ;
if(!vis[f][t]&&dis[f][t]>dis[f][x]+edge[f][i].w){
dis[f][t]=dis[f][x]+edge[f][i].w;
if(!vis[f][t]){
qu.push((node){t,dis[f][t]});
}
}
}
}
}
int main (){
int t;
memset(vis,0,sizeof(vis));
memset(dis,inf,sizeof(dis));
scanf("%d",&t);
while(t--){
scanf("%d%d",&n,&m);
int u,v,w,s;
int ans=0;
for(int i=1;i<=m;++i){
scanf("%d%d%d",&u,&v,&w);
add(0,u,v,w);
add(1,v,u,w);
}
dijkstra(0,1);
dijkstra(1,1);
for(int i=1;i<=n;++i){
ans=ans+dis[0][i]+dis[1][i];
}
printf("%d\n",ans);
memset(vis,0,sizeof(vis));
memset(dis,inf,sizeof(dis));
memset(head,0,sizeof(head));
cnt=1;
}
return 0;
}
```