#include<stdio.h>
#include<algorithm>
#include<vector>
using namespace std;
struct A{
int a, b;
bool operator <(const A &p)const{
return b < p.b;
}
}heap[301000];
vector<int>E[101000], E2[101000];
int n, m, D[101000], top, pv[101000];
int main()
{
scanf("%d%d", &n, &m);
int a, b, c, i, x;
for (i = 0; i < m; i++){
scanf("%d%d%d", &a, &b, &c);
E[a].push_back(c);
E2[b].push_back(a);
}
for (i = 1; i <= n; i++){
if (!E[i].empty())sort(E[i].begin(), E[i].end());
pv[i] = E[i].size();
D[i] = 1999999999;
}
D[n] = 0;
heap[top].a = n, heap[top++].b = 0;
while (1){
while (top && D[heap[0].a] != -heap[0].b){
pop_heap(heap, heap + top);
top--;
}
if (!top)break;
a = heap[0].a, b = D[a];
pop_heap(heap, heap + top);
top--;
for (i = 0; i < E2[a].size(); i++){
x = E2[a][i];
--pv[x];
if (D[x] > b + E[x][pv[x]]){
D[x] = b + E[x][pv[x]];
heap[top].a = x, heap[top++].b = -D[x];
push_heap(heap, heap + top);
}
}
}
printf("%d\n", D[1]);
}
