///先将边存下来在正反分别搜一遍即可
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<queue>
#include<vector>
#include<iostream>
#define inf 2000000000
#define maxn 1100000
using namespace std;
struct Edge
{
    int from,to,cost;
}save[maxn];
vector<int> G[maxn];
vector<Edge> edges;
int dis[maxn],cnt[maxn],n;
bool inq[maxn];
void init()
{
    for(int i=0; i<=n; i++)
        G[i].clear();
    edges.clear();
}
void addEdge(int from,int to,int cost)
{
    Edge eg;
    eg.from=from;
    eg.to=to;
    eg.cost=cost;
    edges.push_back(eg);
    int m=edges.size();
    G[eg.from].push_back(m-1);
}
bool spfa(int s)
{
    for(int i=0; i<=n; i++)dis[i]=inf;
    memset(cnt,0,sizeof(cnt));
    memset(inq,0,sizeof(inq));
    queue<int> que;
    que.push(s);
    dis[s]=0;
    cnt[s]=1;
    inq[s]=true;
    while(!que.empty())
    {
        int tp=que.front();
        que.pop();
        inq[tp]=false;
        for(int i=0; i<G[tp].size(); i++)
        {
            Edge eg = edges[G[tp][i]];
            if(dis[eg.from]<inf&&dis[eg.to]>dis[eg.from]+eg.cost)
            {
                dis[eg.to]=dis[eg.from]+eg.cost;
                if(!inq[eg.to])
                {
                    que.push(eg.to);
                    inq[eg.to]=true;
                    if(++cnt[eg.to]>n)return false;
                }
            }
        }
    }
    return true;

}

int main()
{
    int t,q;
    while(~scanf("%d",&t))
    {
        while(t--)
        {
            scanf("%d%d",&n,&q);
            for(int i=1; i<=q; i++)
            {
                int u,v,c;
                scanf("%d%d%d",&u,&v,&c);
                save[i].from=u,save[i].to=v,save[i].cost=c;
            }
            long long ans=0;
            ///1
            init();
            for(int i=1;i<=q;i++)
                addEdge(save[i].from,save[i].to,save[i].cost);
            spfa(1);
            for(int i=1;i<=n;i++)ans+=dis[i];

            ///2
            init();
            for(int i=1;i<=q;i++)
                addEdge(save[i].to,save[i].from,save[i].cost);
            spfa(1);
            for(int i=1;i<=n;i++)ans+=dis[i];
            printf("%lld\n",ans);
        }

    }
    return 0;
}