#include <iostream>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <string>
#include <map>
#include <iomanip>
#include <algorithm>
#include <queue>
#include <stack>
#include <set>
#include <vector>
//const int maxn = 1e5+5;
#define ll long long
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
ll lcm(ll a,ll b){return a/gcd(a,b)*b;}
//const int inf = 0x6fffffff;
#define MAX INT_MAX
#define FOR(i,a,b) for( int i = a;i <= b;++i)
#define bug cout<<"--------------"<<endl
using namespace std;
ll ver1[1010000],edge1[1010000],edge2[1010000],ver2[1010000],next1[1010000],next2[1010000],head1[1010000],head2[1010000];
ll vis[1010000],d1[1010000],d2[1010000];
ll n,T,m,tot1,tot2;
void add1(ll x,ll y,ll z)
{
ver1[++tot1] = y,edge1[tot1] = z,next1[tot1] = head1[x] , head1[x] = tot1;
}
void add2(ll x,ll y,ll z)
{
ver2[++tot2] = y,edge2[tot2] = z,next2[tot2] = head2[x] , head2[x] = tot2;
}
void dijistra1()
{
priority_queue<pair<ll,ll> >que;
memset(vis,0,sizeof(vis));
memset(d1,1001000000,sizeof(d1));
d1[1] = 0;
que.push(make_pair(0,1));
while(que.size())
{
int x = que.top().second;que.pop();
if(vis[x] == 1) continue;
vis[x] = 1;
for(int i=head1[x] ; i ;i=next1[i])
{
int y = ver1[i];
ll z = edge1[i];
if(d1[y] > d1[x] + z)
{
d1[y] = d1[x] + z;
que.push(make_pair(-d1[y],y));
}
}
}
}
void dijistra2()
{
priority_queue<pair<int,int> >que;
memset(vis,0,sizeof(vis));
memset(d2,1001000000,sizeof(d2));
d2[1] = 0;
que.push(make_pair(0,1));
while(que.size())
{
int x = que.top().second;que.pop();
if(vis[x] == 1) continue;
vis[x] = 1;
for(int i=head2[x] ; i ;i=next2[i])
{
int y = ver2[i];
ll z = edge2[i];
if(d2[y] > d2[x] + z)
{
d2[y] = d2[x] + z;
que.push(make_pair(-d2[y],y));
}
}
}
}
int main()
{
//ios::sync_with_stdio(false);
scanf("%lld",&T);
while(T--)
{
tot1 = 0;
tot2 = 0;
memset(head1,0,sizeof(head1));
memset(head2,0,sizeof(head2));
//cin>>n>>m;
scanf("%lld %lld",&n,&m);
while(m--)
{
ll a,b,z;
scanf("%lld %lld %lld",&a,&b,&z);
add1(a,b,z);
add2(b,a,z);
}
dijistra1();
dijistra2();
ll ans = 0;
for(int i=1;i<=n;++i)
{
ans+=d1[i]+d2[i];
}
printf("%lld
",ans);
}
}