#include<bits/stdc++.h>
using namespace std;
struct road{
	int l,r;		//起点，终点 
	int k;		//路径天数 
}el[1005];
int dis[105];		//每个哨所距离指挥部天数 
int main(){
	int n,m;
	cin>>n>>m;		//n点m边
	for(int i=0;i<m;i++){
		cin>>el[i].l>>el[i].r>>el[i].k;
	} 
	dis[1]=0; 
	for(int i=2;i<=n;i++) dis[i]=114514;		//初始化 
	for(int i=0;i<n-1;i++){
		for(int j=0;j<m;j++){
			dis[el[j].r]=min(dis[el[j].r],dis[el[j].l]+el[j].k);
			dis[el[j].l]=min(dis[el[j].l],dis[el[j].r]+el[j].k);		//双向边 
		}
	}
	int ans=-1;
	for(int i=2;i<=n;i++){
		if(dis[i]==114514){
			cout<<-1<<endl;
			return 0;
		}
		ans=max(ans,dis[i]);
	} 
	cout<<ans<<endl;
	return 0;
}