#include <iostream>

#include <stdio.h>

#include <math.h>

#include <string.h>

#include <queue>

#include <algorithm>

#include <map>

#include <string>

typedef long long LL;

///#define INF 0x3f3f3f3f

#define INF 100000000000000

#define N 1000100

using namespace std;

struct node

{

    int v;

    LL w;

    node(){};

    node(int v, LL w):v(v),w(w){}

};

vector<node > G[N];

vector<node > G1[N];

int vis[N], n, m;

LL dist[N];

LL spfa1(int s)

{

    for(int i=; i<=n; i++)

        dist[i] = INF;

    dist[s] = ;

    queue<int> Q;

    Q.push(s);

    memset(vis, , sizeof(vis));

    vis[s] = ;

    while(!Q.empty())

    {

        int p = Q.front(); Q.pop();

        vis[p] = ;

        for(int i=, len=G[p].size(); i<len; i++)

        {

            node q = G[p][i];

            if(dist[q.v] > dist[p] + q.w)

            {

                dist[q.v] = dist[p] + q.w;

                if(!vis[q.v])

                {

                    vis[q.v] = ;

                    Q.push(q.v);

                }

            }

        }

    }

    LL ans = ;

    for(int i=; i<=n; i++)

        ans += dist[i];

    return ans;

}

LL spfa2(int s)

{

    queue<int>Q;

    for(int i=; i<=n; i++)

        dist[i] = INF;

    memset(vis, , sizeof(vis));

    vis[s] = ;

    dist[s] = ;

    Q.push(s);

    while(!Q.empty())

    {

        int p = Q.front(); Q.pop();

        vis[p] = ;

        for(int i=, len=G1[p].size(); i<len; i++)

        {

            node q = G1[p][i];

            if(dist[q.v] > dist[p] + q.w)

            {

                dist[q.v] = dist[p] + q.w;

                if(!vis[q.v])

                {

                    vis[q.v] = ;

                    Q.push(q.v);

                }

            }

        }

    }

    LL ans = ;

    for(int i=; i<=n; i++)

        ans += dist[i];

    return ans;

}

int main()

{

    int T;

    scanf("%d", &T);

    while(T--)

    {

        scanf("%d %d", &n, &m);

        for(int i=; i<=n; i++)

        {

            G[i].clear();

            G1[i].clear();

        }

        for(int i=; i<=m; i++)

        {

            int u, v; LL w;

            scanf("%d %d %I64d", &u, &v, &w);

            G[u].push_back(node(v, w));

            G1[v].push_back(node(u, w));

        }

        LL ans = spfa1();

        ans += spfa2();

        printf("%I64d\n", ans);

    }

    return ;

}