#include <bits/stdc++.h>
#define f first
#define s second
#define mp make_pair
#define pb push_back
#define lp(i,a,n) for(int i=(a);i<=(int)(n);++i)
#define lpd(i,a,n) for(int i=(a);i>=(int)(n);--i)
#define mem(a,b) memset(a,b,sizeof a)
#define all(v) v.begin(),v.end()
#define println(a) cout <<(a) <<endl
#define sz(x) ((int)(x).size())
#define readi(x) scanf("%d",&x)
#define read2i(x,y) scanf("%d%d",&x,&y)
#define read3i(x,y,z) scanf("%d%d%d",&x,&y,&z)
#define mod 1000000007
#define eps 1e-8
#define infi 1000000000
#define infll 1000000000000000000ll
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vll;
typedef set<int> si;
typedef map<int,int> mii;

const int N = 2002;
int t,n,m;
ll dp[N],dist[N];
struct edge {int fr,to,w;};
vector<edge> edges;
vector<vector<pair<int,int>>> g(N);

ll dfs(int i){
    if(dp[i] != infll) return dp[i];
    dp[i] = infll-1;
    ll ret = infll;
    for(pair<int,int> p : g[i]) ret = min(ret, p.s + dfs(p.f) * (dfs(p.f) < 0));
    return dp[i] = ret;
}

bool negCycle(int src){
    lp(i,1,n) dist[i] = infll;
    dist[src] = 0;

    lp(i,1,n-1){
        bool relax = false;
        for(edge e : edges){
            if(dist[e.fr] + e.w < dist[e.to]){
                dist[e.to] = dist[e.fr] + e.w;
                relax = true;
            }
        }
        if(!relax) break;
    }
    for(edge e : edges){
        if(dist[e.fr] + e.w < dist[e.to])
            return true;
    }
    return false;
}

int main(){
    readi(t);
    while(t--) {
        read2i(n,m);
        lp(i,1,m){
            int a,b,c;
            read3i(a,b,c);
            edges.pb({a,b,c});
        }

        if(negCycle(1)) puts("-inf");
        else{
            ll ans = infll;
            for(edge e : edges){
                ans = min(ans, 1ll*e.w);
                g[e.fr].pb({e.to, e.w});
            }

            lp(i,1,n){
                lp(j,1,n) dp[j] = infll;
                ans = min(ans, dfs(i));
            }
            printf("%I64d\n",ans);
        }

        edges.clear();
        g.clear();
        g.resize(N);
    }
}

/*
freopen("input.txt","r",stdin);
freopen("output.txt","w",stdout);
ios::sync_with_stdio(0);cin.tie(0);
*/