link

#include <iostream>
#include <queue>

#pragma GCC optimize("3", "Ofast", "inline")
#pragma GCC target("avx")

using namespace std;
using ll = long long;

const int kMaxN = 2e5 + 1;

ll t, n, m, dis[kMaxN], h[kMaxN];
struct Node {
  ll u, w;
  bool operator<(const Node &a) const { return w > a.w; }
};
vector<Node> g[kMaxN], o;

bool SPFA() {
  queue<int> q;
  bool f[kMaxN] = {};
  int v[kMaxN] = {};
  q.push(0);
  fill(h + 1, h + n + 1, 1e18);
  while (!q.empty()) {
    int t = q.front();
    q.pop();
    f[t] = 0;
    v[t]++;
    if (v[t] > n) {
      return 0;
    }
    for (auto i : g[t]) {
      if (h[t] + i.w < h[i.u]) {
        h[i.u] = h[t] + i.w;
        if (!f[i.u]) {
          f[i.u] = 1;
          q.push(i.u);
        }
      }
    }
  }
  return 1;
}

void Dijkstra(int st) {
  fill(dis + 1, dis + n + 1, 1e18);
  priority_queue<Node> q;
  bool f[kMaxN] = {};
  q.push({st, 0});
  dis[st] = 0;
  while (!q.empty()) {
    int t = q.top().u;
    q.pop();
    if (f[t]) {
      continue;
    }
    f[t] = 1;
    for (auto i : g[t]) {
      if (dis[t] + i.w < dis[i.u]) {
        dis[i.u] = dis[t] + i.w;
        q.push({i.u, dis[i.u]});
      }
    }
  }
}

void S() {
  cin >> n >> m;
  for (int i = 1, u, v, w; i <= m; i++) {
    cin >> u >> v >> w;
    g[u].push_back({v, w});
  }
  for (int i = 1; i <= n; i++) {
    g[0].push_back({i, 0});
  }
  if (!SPFA()) {
    cout << "-inf\n";
    return;
  }
  for (int i = 1; i <= n; i++) {
    for (auto &j : g[i]) {
      j.w += h[i] - h[j.u];
    }
  }
  ll ans = 1e18;
  for (int i = 1; i <= n; i++) {
    Dijkstra(i);
    for (int j = 1; j <= n; j++) {
      ans = min(ans, (dis[j] == 1e18 ? dis[j] : dis[j] + h[j] - h[i]));
    }
  }
  cout << ans << '\n';
}

int main() {
  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  for (cin >> t; t; t--) {
    S();
    fill(g, g + n + 1, o);
  }
  return 0;
}