#include<iostream>
#include<cstring>
using namespace std;
#define int long long
const int N=1e6+10,INF=0x3f3f3f3f;
struct ltt_node{
    int lson,rson;
    int val,tag;
    int from,to;
    int dis;
};
struct leftist_tree{
    ltt_node ltt[N];
    int tot;
    inline int newnode(int val,int from,int to){
        tot++;
        ltt[tot] = ltt_node {0, 0, 0, 0, 0, 0, 0};
        ltt[tot].val=val;
        ltt[tot].from=from;
        ltt[tot].to=to;
        return tot;
    }
    inline void pushdown(int now){
        int ls=ltt[now].lson,rs=ltt[now].rson;
        ltt[ls].val+=ltt[now].tag;
        ltt[rs].val+=ltt[now].tag;
        ltt[ls].tag+=ltt[now].tag;
        ltt[rs].tag+=ltt[now].tag;
        ltt[now].tag=0;
    }
    int merge(int x,int y){
        if(!x||!y) return x+y;
        pushdown(x),pushdown(y);
        if(ltt[x].val>ltt[y].val) swap(x,y);
        ltt[x].rson=merge(ltt[x].rson,y);
        if(ltt[ltt[x].rson].dis>ltt[ltt[x].lson].dis)
            swap(ltt[x].lson,ltt[x].rson);
        ltt[x].dis=ltt[ltt[x].rson].dis+1;
        return x;
    }
    int del(int rt){
        pushdown(rt);
        int ls=ltt[rt].lson;
        int rs=ltt[rt].rson;
        return merge(ls,rs);
    }
};//左偏树基本操作
leftist_tree ltt;
int root[N],fa[N];
int sta[N],top;
bool vis[N];
inline int find(int x){
    return x==fa[x]?x:fa[x]=find(fa[x]);
}//并查集，用于查找一个点被收缩多次后的新点
signed main(){

    // freopen(".in", "r", stdin);
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    int T;
    for(cin >> T; T--; ) {
        for(int i = 1; i <= top; ++i) sta[i] = vis[i] = 0;
        int n,m,r = 1;
        ltt.tot = 0;
        cin>>n>>m;
        for(int i = 1; i <= n * 2; ++i) root[i] = fa[i] = sta[i] = vis[i] = 0;
        for(int i=1;i<=m;i++){
            int x,y,z;
            cin>>x>>y>>z;
            int lp=ltt.newnode(z,x,y);//新建一个左偏树节点，边从x到y，边权为z
            root[y]=ltt.merge(root[y],lp);//插入到y的左偏树中
        }
        for(int i=1;i<=n;i++){
            int x=i,y=i%n+1;
            int p=ltt.newnode(INF,x,y);
            root[y]=ltt.merge(root[y],p);
        }//加入n条边强行使其强连通
        for(int i=1;i<=2*n;i++) fa[i]=i;//算上收缩的点共有2n个点
        sta[++top]=r,vis[r]=true;
        int ans=0,cnt=n;
        while(root[sta[top]]){//还有边
            int lp=root[sta[top]];
            ltt_node tmp=ltt.ltt[lp];
            int u=find(tmp.from);
            if(u==sta[top]){
                root[sta[top]]=ltt.del(root[sta[top]]);
                continue;
            }//自环
            if(!vis[u]){
                sta[++top]=u;
                vis[u]=true;
                continue;
            }//不构成环，加入即可
            int p=++cnt;//把环缩为p
            while(vis[u]){//u还没被弹出
                int v=sta[top--];//环上的节点
                vis[v]=false,fa[v]=p;//这个点缩成了p
                int val=ltt.ltt[root[v]].val;//最短弧的边权
                ltt.ltt[root[v]].tag-=val;//懒标记
                int x=find(ltt.ltt[root[v]].to);
                ans+=(x!=find(r))*val;//如果x等于r，说明这条边通向r，不能选
                root[v]=ltt.del(root[v]);//删掉最短弧
                root[p]=ltt.merge(root[p],root[v]);//合并到p的左偏树上
            }//把整个环找出来
            sta[++top]=p;
            vis[p]=true;//把p加入
        }
        cout<<(ans>=INF?-1:ans)<<'\n';
    }
}