#include<bits/stdc++.h> using namespace std; const int N=510,M=100010; int h[N],e[M],ne[M],w[M],idx; int state[N]; int dist[N]; int n,m; void add(int a,int b,int c){ e[idx]=b,w[idx]=c,ne[idx]=h[a],h[a]=idx++; } void Dijkstra(){ 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(!state[j]&&(t==-1||dist[j]<dist[t])) t=j; state[t]=1; for(int j=h[j];j!=-1;j=ne[j]){ int v=e[j]; dist[v]=min(dist[v],dist[t]+w[j]); } } } int main(){ memset(h,-1,sizeof h); cin>>n>>m; while(m--){ int a,b,w; cin>>a>>b>>w; add(a,b,w); } Dijkstra(); if(dist[n]!=0x3f3f3f3f) cout<<dist[n]; else cout<<-1; return 0; }