#include <bits/stdc++.h>
using namespace std;
#define int long long
#define maxn 100050
#define pii pair<int,int>
#define f first
#define s second
int32_t main() {
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
int no_of_vertex,no_of_edge;
int input1,input2,input3;
vector<vector<int> > adj(maxn);
cin >> no_of_vertex >> no_of_edge;
vector<vector<int> > num(maxn);
for(int i=0;i<no_of_edge;i++){
cin >> input1 >> input2 >> input3;
adj[input2].push_back(input1);
num[input1].push_back(input3);
}
vector<int> dist(maxn,INT_MAX);
dist[no_of_vertex] = 0;
for(int i=0;i<maxn;i++){
sort(num[i].begin(),num[i].end());
}
priority_queue<pii,vector<pii>,greater<pii> > q1;
q1.push({0,no_of_vertex});
while(q1.size()!=0){
pair<int,int> a = q1.top();
q1.pop();
if(dist[a.s]!=a.first){
continue;
}
for(auto k:adj[a.second]){
if(dist[k]>a.first+num[k].back()){
dist[k] = a.first+num[k].back();
q1.push({dist[k],k});
}
num[k].pop_back();
}
}
/*for(int i=1;i<=no_of_vertex;i++){
cout << dist[i] << " ";
}
cout << endl;*/
cout << dist[1];
}
