UVa Q721

//UVa Q721
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int MAXN = 1e6+1;

struct stat{
    int v, w;
    bool operator>(const stat &x)const{return w > x.w;}
};
vector<stat> e1[MAXN];
vector<stat> e2[MAXN];
int ans1[MAXN];
int ans2[MAXN];

int32_t main(){
    int t,n,m;
    cin >> t;
    while(t--){
        cin >> n >> m;
        for(int i = 1; i <= n; ++i){
            e1[i].clear();
            e2[i].clear();
            ans1[i] = ans2[i] = 1e18;
        }
        for(int i = 0; i < m; ++i){
            int a,b,c;
            cin >> a >> b >> c;
            stat aux={.v = b, .w = c};
            e1[a].emplace_back(aux);
            aux.v = a;
            e2[b].emplace_back(aux);
        }
        priority_queue<stat, deque<stat>, greater<stat> > pq1, pq2;
        stat tmd={.v = 1, .w = 0};
        pq1.push(tmd);
        pq2.push(tmd);
        while(!pq1.empty()){
            tmd = pq1.top();
            pq1.pop();
            //cout << tmd.v << ' ' << tmd.w << ' ' << endl;
            if(ans1[tmd.v] == 1e18)ans1[tmd.v] = tmd.w;
            for(unsigned i = 0; i < e1[tmd.v].size(); ++i){
                if(ans1[e1[tmd.v][i].v] != 1e18)continue;
                stat nxt = e1[tmd.v][i];
                nxt.w += tmd.w;
                pq1.push(nxt);
            }
        }
        /*for(int i = 1; i <= n; ++i){
            cout << ans1[i] << ' ';
        }
        cout << endl;*/
        while(!pq2.empty()){
            tmd = pq2.top();
            pq2.pop();
            //cout << tmd.v << ' ' << tmd.w << ' ' << endl;
            if(ans2[tmd.v] == 1e18)ans2[tmd.v] = tmd.w;
            for(unsigned i = 0; i < e2[tmd.v].size(); ++i){
                if(ans2[e2[tmd.v][i].v] != 1e18)continue;
                stat nxt = e2[tmd.v][i];
                nxt.w += tmd.w;
                pq2.push(nxt);
            }
        }
        /*for(int i = 1; i <= n; ++i){
            cout << ans2[i] << ' ';
        }
        cout << endl;*/
        int out = 0;
        for(int i = 1; i <= n; ++i)out += ans1[i]+ans2[i];
        cout << out << '\n';
    }
    return 0 ;
}