#include<iostream>
#include<fstream>
#include<vector>
#include<queue>
#include<stack>
#include<math.h>
#include<algorithm>
#include<map>
#include<set>
#include<unordered_map>
#include<unordered_set>
using namespace std;

#define official

#ifdef official
#define cin inF
#define cout outF
#endif

ifstream inF("graph.in");
ofstream outF("graph.out");

const int MAX_N=1100;
struct Edge
{
    int f,t;
    long long w;
};
vector<int> ne[MAX_N];
Edge e[MAX_N];
long long ub[MAX_N][MAX_N]; //fi <= fj + ub[i][j]
long long lb[MAX_N][MAX_N]; //fi >= fj + lb[i][j]
long long inf=1e18;
int n,m;
long long ans;
bool ansisinf;


void input()
{
    cin>>n>>m;
    int a,b;
    for (int i=0;i<m;++i)
    {
        cin>>a>>b>>e[i].w;
        --a;
        --b;
        e[i].f=a;
        e[i].t=b;
        ne[a].push_back(b);

    }
}
void output()
{
    if (ansisinf==0) cout<<ans<<'\n';
    else cout<<"-inf\n";
}

bool vis[MAX_N];

void DFS(int a)
{
    if (ansisinf==0) return;
    if (vis[a])
    {
        ansisinf=0;
        return;
    }
    vis[a]=1;
    for (int i=0;i<ne[a].size();++i)
    {
        DFS(ne[a][i]);
    }
}

bool check(int mw)
{
    for (int i=0;i<n;++i)
    {
        for (int j=0;j<n;++j)
        {
            ub[i][j]=inf;
            lb[i][j]=-inf;
        }
    }
    int a,b,w;
    //cerr<<m<<endl;
    for (int i=0;i<m;++i)
    {
        a=e[i].f;
        b=e[i].t;
        w=e[i].w;
        ub[a][b]=mw-w;
        lb[b][a]=w-mw;
        //cerr<<a<<" "<<b<<" "<<ub[a][b]<<endl;
    }
    /*for (int i=0;i<n;++i)
    {
        for (int j=0;j<n;++j)
        {
            cerr<<ub[i][j]<<' ';
        }
        cerr<<endl;
    }
    cerr<<endl;
    for (int i=0;i<n;++i)
    {
        for (int j=0;j<n;++j)
        {
            cerr<<lb[i][j]<<' ';
        }
        cerr<<endl;
    }
    cerr<<endl;*/
    int cnt=0;
    for (int k=0;k<n;++k)
    {
        for (int i=0;i<n;++i)
        {
            for (int j=0;j<n;++j)
            {
                if (ub[i][k]+ub[k][j]<ub[i][j]) ub[i][j]=ub[i][k]+ub[k][j];
                if (lb[i][k]+lb[k][j]>lb[i][j]) lb[i][j]=lb[i][k]+lb[k][j];
            }
        }
    }
    /*for (int i=0;i<n;++i)
    {
        for (int j=0;j<n;++j)
        {
            cerr<<ub[i][j]<<' ';
        }
        cerr<<endl;
    }
    cerr<<endl;
    for (int i=0;i<n;++i)
    {
        for (int j=0;j<n;++j)
        {
            cerr<<lb[i][j]<<' ';
        }
        cerr<<endl;
    }
    cerr<<endl;*/
    for (int i=0;i<n;++i)
    {
        if (ub[i][i]<0 || lb[i][i]>0) return 0;
    }
    for (int i=0;i<n;++i)
    {
        for (int j=i+1;j<n;++j)
        {
            if (ub[i][j]<lb[i][j]) return 0;
        }
    }
    return 1;
}

void solve()
{
    ansisinf=1;
    for (int i=0;i<n && ansisinf;++i)
    {
        if (vis[i]==0) DFS(i);
    }
    if (ansisinf==1) return;
    /*long long l=-1e13;
    long long r=1e13;*/
    long long l=-10;
    long long r=10;
    long long mid;
    long long last;
    while (l<=r)
    {
        mid=(l+r)/2;
        //cerr<<l<<" "<<r<<" "<<mid<<endl;
        if (check(mid)==1)
        {
            last=mid;
            r=mid-1;
        }
        else
        {
            l=mid+1;
        }
    }
    ans=last;
}

int main()
{
    input();
    solve();
    output();

    return 0;
}