#include <bits/stdc++.h>
using namespace std;
#define int long long
int32_t main() {
ios::sync_with_stdio(false);
cin.tie(0);
int n , m;
cin >> n >> m;
vector<vector<pair<int , int>>> adj(n) , rev(n);
for (int i = 0 ; i < m ; i += 1) {
int a , b , c;
cin >> a >> b >> c;
a -= 1 , b -= 1;
adj[a].emplace_back(b , c);
rev[b].emplace_back(a , c);
}
#define pi pair<int , int>
priority_queue<pi , vector<pi> , greater<pi>> pq;
const int INF = (int)1e18;
vector<int> d(n , INF);
d[n - 1] = 0;
pq.emplace(d[n - 1] , n - 1);
while (!pq.empty()) {
auto t = pq.top();
pq.pop();
if (d[t.second] != t.first) continue;
for (int i = 0 ; i < (int)rev[t.second].size() ; i += 1) {
auto node = rev[t.second][i];
vector<int> c1;
vector<pair<int , int>> c2;
for (auto x : adj[node.first]) {
c1.push_back(x.second);
c2.emplace_back(d[x.first] , x.first);
}
sort(c1.begin() , c1.end());
sort(c2.begin() , c2.end());
for (int j = 0 ; j < (int)c1.size() ; j++) {
int new_id = (int)c1.size() - j - 1;
int id = c2[new_id].second;
if (id == t.second) {
if (d[node.first] > t.first + c1[j]) {
d[node.first] = t.first + c1[j];
pq.emplace(d[node.first] , node.first);
}
break;
}
else continue;
}
}
}
cout << d[0] << '\n';
return 0;
}
