// Author: Klay Thompson
// Problem: P4716 【模板】最小树形图
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P4716
// Memory Limit: 250 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
#ifdef dbg
#define D(...) fprintf(stderr, __VA_ARGS__)
#define DD(...) D(#__VA_ARGS__ " = "), debug_helper::debug(__VA_ARGS__), D("\n")
#include "C:\Users\wsyear\Desktop\OI\templates\debug.hpp"
#else
#define D(...) ((void)0)
#define DD(...) ((void)0)
#endif
#define rep(i, j, k) for (int i = (j); i <= (k); ++i)
#define per(i, j, k) for (int i = (j); i >= (k); --i)
#define SZ(v) int((v).size())
#define ALL(v) (v).begin(),(v).end()
#define fi first
#define se second
using ll = long long;
using pii = std::pair<int, int>;
using pll = std::pair<ll, ll>;

using namespace std;

const int inf = 1E9;
const int N = 400010;
const int M = 500010;

namespace Edmonds {
  
  struct ltt_node {
    int lson, rson;
    int val, tag;
    int from, to;
    int dis;
  };
  
  struct leftist_tree {
    
    ltt_node ltt[M];
    int tot;
    
    void init() {
      rep (i, 1, tot) {
        ltt[i].lson = ltt[i].rson = 0;
        ltt[i].val = ltt[i].tag = 0;
        ltt[i].from = ltt[i].to = 0;
        ltt[i].dis = 0;
      }
      tot = 0;
    }
    
    int newnode(int val, int from, int to) {
      tot++;
      ltt[tot].val = val;
      ltt[tot].from = from;
      ltt[tot].to = to;
      return tot;
    }
    
    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];
  
  int find(int x) {
    return x == fa[x] ? x : fa[x] = find(fa[x]);
  }
  
  void add_edge(int u, int v, int w) {
    int lp = ltt.newnode(w, u, v);
    root[v] = ltt.merge(root[v], lp);
  }
  
  int dmst(int n, int r) {
    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);
    }
    for (int i = 1; i <= 2 * n; i++) fa[i] = i;
    
    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;
      while (vis[u]) {
        int v = sta[top--];
        vis[v] = false, fa[v] = 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;
        root[v] = ltt.del(root[v]);
        root[p] = ltt.merge(root[p], root[v]);
      }
      
      sta[++top] = p, vis[p] = true;
    }
    return ans;
  }
}

int n, m, rt;

void work() {
  cin >> n >> m, rt = 1;
  fill(Edmonds::root + 1, Edmonds::root + 2 * n + 1, 0);
  fill(Edmonds::fa + 1, Edmonds::fa + 2 * n + 1, 0);
  fill(Edmonds::sta + 1, Edmonds::sta + 2 * n + 1, 0);
  fill(Edmonds::vis + 1, Edmonds::vis + 2 * n + 1, false);
  Edmonds::top = 0, Edmonds::ltt.init();
  rep (i, 1, m) {
    int u, v, w; cin >> u >> v >> w;
    Edmonds::add_edge(u, v, w);
  }
  ll ans = Edmonds::dmst(n, rt);
  cout << (ans >= inf ? -1 : ans) << '\n';
}

int main() {
  cin.tie(nullptr) -> ios::sync_with_stdio(false);
  int t; cin >> t;
  while (t--) work();
}