/**********************************************
 *Author*        :jxf378440404
 *Created Time*  : 2019/8/24 14:46:44

*********************************************/

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <string>
#include <cmath>
#include <algorithm>
#include <vector>
#include <map>
#include <queue>
#include <set>
#define fi first
#define se second
using namespace std;
typedef long long LL;
typedef pair<LL, int> PII;
const int MaxN = 1e3;
const LL Inf = 1LL << 60;

LL dis[MaxN + 5];
int id[MaxN + 5], Size[MaxN + 5];
bool vis[MaxN + 5];
vector<PII> G[MaxN + 5];
PII now, nxt;
struct cmp{
    bool operator() (PII A, PII B) {
        return A.fi > B.fi;
    }
};
priority_queue<PII, vector<PII>, cmp> q;

int n;
LL dij(int x) {
    LL ans = 0;
    while(!q.empty()) q.pop();
    for(int i = 1; i <= n; ++i) {
        dis[i] = Inf;
        id[i] = 0;
        vis[i] = false;
    }
    dis[x] = 0LL;
    now.se = x; now.fi = 0LL;
    q.push(now);
    while(!q.empty()) {
        now = q.top(); q.pop();
        if(vis[now.se]) continue;
        vis[now.se] = true;
        for(int i = 0; i < Size[now.se]; ++i) {
            nxt = G[now.se][i];
            if(dis[nxt.se] > dis[now.se] + nxt.fi) {
                dis[nxt.se] = dis[now.se] + nxt.fi;
                if(now.se != x) id[nxt.se] = max(id[now.se], now.se);
                else id[nxt.se] = id[now.se];
                nxt.fi = dis[nxt.se];
                q.push(nxt);
            }
            else if(dis[nxt.se] == dis[now.se] + nxt.fi) {
                if(now.se != x) id[nxt.se] = min(id[nxt.se], max(id[now.se], now.se));
                else id[nxt.se] = min(id[nxt.se], id[now.se]);
            }
        }
    }
    for(int i = 1; i <= n; ++i) ans += (LL)id[i];
    return ans;
}

int main()
{
    LL ans;
    int m, u;
    int T; scanf("%d", &T);
    while(T--) {
        scanf("%d %d", &n, &m);
        for(int i = 1; i <= m; ++i) {
            scanf("%d %d %I64d", &u, &now.se, &now.fi);
            G[u].push_back(now);
            swap(u, now.se);
            G[u].push_back(now);
        }
        for(int i = 1; i <= n; ++i) Size[i] = G[i].size();
        ans = 0;
        for(int i = 1; i <= n; ++i) ans += dij(i);
        printf("%I64d\n", ans);
        for(int i = 1; i <= n; ++i) G[i].clear();
    }
    return 0;
}