#include<bits/stdc++.h>
using namespace std;
int n,m,a[2500][2500]={0,0};
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++){
		int u,v,w;
		scanf("%d%d%d",&u,&v,&w);
		if(a[u][v]<w)
			a[u][v]=w;
	}
	for(int k=1;k<=n;k++){
		for(int i=1;i<=n;i++){
			for(int j=1;j<=n;j++){
				if((i!=j)&&(i!=k)&&(k!=j)&&(a[i][j]!=0)&&(a[i][k]!=0)&&(a[k][j]!=0)&&(a[i][j]<a[i][k]+a[k][j])){
					a[i][j]=a[i][k]+a[k][j];
				}
			}
		}
	}
	if(a[1][n]==0)
		cout<<"-1";
	else
		cout<<a[1][n];
} 

求求各位大佬帮忙解惑