#include<bits/stdc++.h>
using namespace std;
#define int long long
struct Edge{int v, c;};
#define pii pair<long long , int>
signed main(){
int n , m;
cin>>n>>m;
vector<vector<Edge>> rev_g(n+1);
vector<vector<int>> cost(n+1);
for(int i = 0 ; i< m ;i++){
int u , v , c;
cin>>u>>v>>c;
rev_g[v].push_back({u , c});
cost[u].push_back(c);
}
for(int i = 1; i<=n;i++){
sort(cost[i].begin() , cost[i].end());
}
priority_queue<pii , vector<pii>, greater<pii>> pq;
pq.push({0 , n});
vector<int> dist(n + 1, LLONG_MAX/4) , seen(n+1);
dist[n]=0;
while(!pq.empty()){
int d = pq.top().first;
int u = pq.top().second;
pq.pop();
if(d != dist[u])continue;
for(auto v : rev_g[u]){
seen[v.v]++;
int k = cost[v.v].size();
int cand = dist[u] + cost[v.v][k - seen[v.v]];
if(cand < dist[v.v]){
dist[v.v] = cand;
pq.push({dist[v.v] , v.v});
}
}
}
cout<<dist[1];
}
