#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <cmath>

#include <algorithm>

#include <assert.h>

#define IOS ios::sync_with_stdio(false)

using namespace std;

#define inf (0x3f3f3f3f)

typedef long long int LL;

#include <iostream>

#include <sstream>

#include <vector>

#include <set>

#include <map>

#include <queue>

#include <string>

#include <bitset>

struct HeapNode {

    int u, dis;

    HeapNode(int from, int cost) : u(from), dis(cost) {}

    bool operator < (const struct HeapNode & rhs) const {

        return dis > rhs.dis;

    }

};

const int maxn =  + ;

int book[maxn], DFN, dis[maxn];

int first[maxn], num;

struct Node {

    int u, v, w, tonext;

}e[maxn * ];

void add(int u, int v, int w) {

    ++num;

    e[num].u = u, e[num].v = v, e[num].w = w;

    e[num].tonext = first[u];

    first[u] = num;

}

void dij(int bx, int n) {

    ++DFN;

    for (int i = ; i <= n; ++i) dis[i] = inf;

    dis[bx] = ;

    priority_queue<HeapNode> que;

    while (!que.empty()) que.pop();

    que.push(HeapNode(bx, dis[bx]));

    while (!que.empty()) {

        HeapNode t = que.top();

        que.pop();

        int u = t.u;

        if (book[u] == DFN) continue;

        book[u] = DFN;

        for (int i = first[u]; i; i = e[i].tonext) {

            int v = e[i].v;

            if (book[v] != DFN && dis[v] > dis[u] + e[i].w) {

                dis[v] = dis[u] + e[i].w;

                que.push(HeapNode(v, dis[v]));

            }

        }

    }

}

bool in[maxn], tim[maxn];

bool spfa(int bx, int n) { //从bx开始，有n个顶点

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

        dis[i] = inf;

        tim[i] = ; //入队次数清0

        in[i] = false; //当前这个节点不在队列里

    }

    queue<int> que;

    while (!que.empty()) que.pop();

    que.push(bx), in[bx] = true, dis[bx] = , tim[bx]++;

    while (!que.empty()) {

        int u = que.front();

        if (tim[u] > n) return true; //出现负环

        que.pop();

        for (int i = first[u]; i; i = e[i].tonext) {

            if (dis[e[i].v] > dis[e[i].u] + e[i].w) {

                dis[e[i].v] = dis[e[i].u] + e[i].w;

                if (!in[e[i].v]) { //不在队列

                    que.push(e[i].v);

                    in[e[i].v] = true;

                    tim[e[i].v]++;

                }

            }

        }

        in[u] = false;

    }

    return false;

}

int u[maxn], v[maxn], w[maxn];

void init(int n) {

    for (int i = ; i <= n; ++i) first[i] = ;

    num = ;

}

void work() {

    int n, m;

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

    init(n);

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

//        cin >> u[i] >> v[i] >> w[i];

        scanf("%d%d%d", &u[i], &v[i], &w[i]);

        add(u[i], v[i], w[i]);

    }

    spfa(, n);

    LL ans = ;

    for (int i = ; i <= n; ++i) ans += dis[i];

    init(n);

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

        add(v[i], u[i], w[i]);

    }

    spfa(, n);

    for (int i = ; i <= n; ++i) ans += dis[i];

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

}

int main() {

#ifdef local

    freopen("data.txt", "r", stdin);

//    freopen("data.txt", "w", stdout);

#endif

    int t;

    scanf("%d", &t);

    while (t--) work();

    return ;

}