#include<bits/stdc++.h> using namespace std; int t,n,m,x,y,z,id; struct o{ int x,y; }; bool operator <(o x,o y){ return x.x>y.x; } int dis[300005]; int vis[300005]; int last[300005],v[300005],pre[300005],d[300005]; priority_queue<o> q; void add(int x,int y,int z){ v[++id]=y,pre[id]=last[x],d[id]=z; last[x]=id; } void dij(int x){ memset(dis,0x3f,sizeof dis); dis[1]=0; q.push({0,x}); while(!q.empty()){ int u=q.top().y; q.pop(); if(vis[u])continue; //for(int j=1;j<=n;j++)if(vis[j]==0&&dis[j]<dis[u])u=j; vis[u]=1; for(int j=last[u];j;j=pre[j])if(vis[v[j]]==0&&dis[u]+d[j]<dis[v[j]])dis[v[j]]=dis[u]+d[j],q.push({dis[v[j]],v[j]}); } } int main(){ freopen("dijkstra.in","r",stdin); freopen("dijkstra.out","w",stdout); cin>>n>>m; for(int i=0;i<m;i++)cin>>x>>y>>z,add(x,y,z); dij(1); if(dis[n]<0x3f3f3f3f)cout<<dis[n]; else cout<<-1; return 0; }