#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define int ll
#define rep(i,a,b) for (int i = a; i < (b); i++)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
#define PB push_back
#define FS first
#define SD second
#define ary(k) array<int, k>
template<class A, class B> void cmx(A &x, B y) { x = max<A>(x, y);}
template<class A, class B> void cmn(A &x, B y) { x = min<A>(x, y);}
typedef pair<int, int> pii;
typedef vector<int> vi;
int n,m,w[1<<20][5],d[1<<20],I=1e18;
int C(int k){
	for(int i=1;i<n;i++)
		d[i]=-1;
	d[n]=k;
	for(int j=1;j<=n;j++)
		for(int i=1;i<=m;i++){
			int x=w[i][0],y=w[i][1],z=w[i][2];
			if(d[x]==-1)
				continue;
			if(d[x]+z>=0)
				d[y]=max(d[y],d[x]+z);
		}
	for(int i=1;i<=m;i++){
		int x=w[i][0],y=w[i][1],z=w[i][2];
		if(d[x]==-1)
			continue;
		if(d[y]<d[x]+z)
			d[y]=I;
	}
	for(int j=1;j<=n;j++)
		for(int i=1;i<=m;i++){
			int x=w[i][0],y=w[i][1],z=w[i][2];
			if(d[x]==I)
				d[y]=I;
		}
	return d[1]!=-1;
}
signed main() {
	cin.tie(0)->sync_with_stdio(0); cin.exceptions(cin.failbit);
	cin>>n>>m;
	for(int i=1;i<=m;i++)
		cin>>w[i][1]>>w[i][0]>>w[i][2],w[i][2]=-w[i][2];
	int l=0,r=I,d;
	while(l<r)
		d=(l+r)/2,C(d)?r=d:l=d+1;
	cout<<l<<'\n';
}