#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define MAXN (1000005)
int main() {
ios_base::sync_with_stdio(false);cin.tie(0);
ll N,M;
cin>>N>>M;
vector<pair<ll,ll> > fromn[N];
priority_queue<ll> in[N];//unassigned costs of incoming edges to i
for(ll i = 0;i < M;i++){
ll a,b,c;
cin>>a>>b>>c;
a--;
b--;
fromn[b].push_back(make_pair(c,a));
in[a].push(c); //in the original direction
}
priority_queue<pair<ll,ll>,vector<pair<ll,ll> >,greater<pair<ll,ll> > > pq;
ll dist[N];
memset(dist,-1,sizeof(dist));
pq.push(make_pair(0,N - 1));
dist[N - 1] = 0;
while(!pq.empty()){
pair<ll,ll> x = pq.top();
pq.pop();
if(x.first != dist[x.second]){
continue;
}
for(auto u : fromn[x.second]){
ll maximum = in[u.second].top();
u.first = maximum;
in[u.second].pop();
if(dist[u.second] == -1 || dist[u.second] > dist[x.second] + u.first){
dist[u.second] = dist[x.second] + u.first;
pq.push(make_pair(dist[u.second],u.second));
}
}
}
cout<<dist[0]<<'\n';
}
