#include <bits/stdc++.h>

using namespace std;

typedef long long llint;

const int MAXN = 1001;
const llint INF = 1ll<<31;

struct
{
	int u, v;
	llint c;
} edges[MAXN];
llint dist[MAXN];

int main()
{
	freopen("graph.in", "r", stdin);
	freopen("graph.out", "w", stdout);
	
	int n, m, i, j;
	int u, v;
	llint c;
	llint sol = -1<<30;
	
	cin>>n>>m;
	
	for (i = 0; i < m; ++i)
	{
		cin>>edges[i].u>>edges[i].v>>edges[i].c;
	}
	
	llint lo = -INF, hi = INF, mid;
	while (hi - lo > 1)
	{
		mid = (hi + lo) / 2;
		
		for (i = 0; i < m; ++i)
		{
			edges[i].c += mid;
		}
		dist[0] = 0;
		for (i = 1; i < n; ++i)
			dist[i] = INF;
		
		for (i = 0; i < n; ++i)
		{
			for (j = 0; j < m; ++j)
				if (dist[edges[j].u] + edges[j].c < dist[edges[j].v])
					dist[edges[j].v] = dist[edges[j].u] + edges[j].c;
		}
		bool ok = true;
		for (j = 0; j < m; ++j)
			if (dist[edges[j].u] + edges[j].c < dist[edges[j].v])
			{
				ok = false;
				break;
			}
		
		if (ok)
			hi = mid;
		else lo = mid;
		
		for (i = 0; i < m; ++i)
		{
			edges[i].c -= mid;
		}
	}
	
	if (lo != -INF)
		cout<<-hi<<'\n';
	else cout<<"-inf\n";
}