#include<bits/stdc++.h>
#define int long long
#define fast ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
using namespace std;

void solve();

signed main() {
    fast
    int t = 1;
    cin >> t;
    while (t--) solve();
}
const int maxn=500010;
struct A{int x,y,z;};
A e[maxn];
int v[maxn];
int n,m,id=0;
void add(int x,int y,int z)
{
    e[++id]={x,y,z};
}
bool comp(A p,A q)
{
    return p.x<q.x;
}
int ch()
{
    int ans=0;
    sort(e+1,e+id+1,comp);
    for(int i=1;i<=m;i++)
    {
       if(!v[e[i].y])
       {
           v[e[i].y]=1;
           ans+=e[i].z;
       }
    }
    return ans;
}
void solve() {
    id=0;
    cin>>n>>m;
    int xi,yi,zi;
    for(int i=1;i<=n;i++)
    {
        v[i]=0;
    }
    for(int i=1;i<=m;i++)
    {
        int x,y,z;
        cin>>x>>y>>z;
        if(x<y)add(x,y,z);
        else
        {
            xi=x;
            yi=y;
            zi=z;
        }
    }
    int ans=ch();
    for(int i=1;i<=n;i++)v[i]=0;
    v[yi]=1;
    ans=min(ans,zi+ch());
    cout<<ans<<"\n";
}