#include<bits/stdc++.h>
using namespace std;
vector<pair<int,int>>e[2001];
long long dis[2001];
bool inQ[2001];
int tim[2001];
int Q[4000001];
int main(){
    int n,m;
    scanf("%d %d",&n,&m);
    for(int i=1;i<=m;i++)
    {
        int u,v,w;
        scanf("%d %d %d",&u,&v,&w);
        e[v].push_back({u,-w});
    }
    auto check=[&](const long long &val)->bool
    {
        memset(dis,-0x3f,sizeof(dis));
        memset(tim,0,sizeof(tim));
        memset(inQ,false,sizeof(inQ));
        int head=1,tail=0;
        Q[++tail]=n;inQ[n]=true;tim[n]=1;
        dis[n]=val;
        while(head<=tail)
        {
            int u=Q[head++];
            inQ[u]=false;
            for(auto [v,w]: e[u])
            {
                if(dis[u]+w<0)
                    continue;
                if(dis[v]<dis[u]+w)
                {
                    dis[v]=dis[u]+w;
                    tim[v]=tim[u]+1;
                    if(tim[v]>=n)
                        return true;
                    if(!inQ[v])
                    {
                        inQ[v]=true;
                        Q[++tail]=v;
                    }
                }
            }
        }
        return dis[1]>=0;
    };
    long long l=0,r=1e18,ans=-1;
    while(l<=r)
    {
        long long mid=(l+r)>>1;
        if(check(mid))
        {
            ans=mid;
            r=mid-1;
        }
        else
            l=mid+1;
    }
    printf("%lld\n",ans);
    
    return 0;
}