#include<bits/stdc++.h> using namespace std; int n,m,g[2001][2001],dist[10001]; bool st[10001]; int D(){ memset(dist,0x3f,sizeof dist); dist[1]=0; for(int i=1;i<=n;i++){ int t=-1; for(int j=1;j<=n;j++){ if(!st[j]&&(t==-1||dist[j]<dist[t])) t=j; } st[t]=1; for(int j=1;j<=n;j++){ dist[j]=min(dist[j],dist[t]+g[t][j]); } } if(dist[n]==0x3f3f3f) return-1; return dist[n]; } int main(){ cin>>n>>m; int a,b; for(int i=1;i<=m;i++){ cin>>a>>b; cin>>g[a][b]; } cout<<D(); return 0; }