#include <bits/stdc++.h>
using namespace std ;
const int N = 1e5 + 2 ;
vector < pair < int, int > > adj[N], rev[N] ;
vector < int > edgeCosts[N] ;
int main()
{
int n, m, u, v, c ; cin >> n >> m ;
for(int i = 0; i < m; i++)
{
cin >> u >> v >> c ;
rev[v].push_back({u, c});
edgeCosts[u].push_back(c);
}
for(int i = 1; i <= n; i++)
sort(edgeCosts[i].begin(), edgeCosts[i].end());
int dist[n+1] ; for(int i = 0; i <= n; i++) dist[i] = 2e9 ;
set < pair < int, int > > heap ; heap.insert({0, n});
while(!heap.empty())
{
int top = (*heap.begin()).second, cst = (*heap.begin()).first ;
heap.erase(heap.begin());
for(auto grp : rev[top])
{
int cost = edgeCosts[grp.first].back() ;
if((cst + cost) < dist[grp.first])
{
heap.erase({dist[grp.first], grp.first});
dist[grp.first] = cst + cost ;
heap.insert({dist[grp.first], grp.first});
edgeCosts[grp.first].pop_back();
}
}
}
cout << dist[1] ;
return 0;
}
