#include <iostream>
#include <fstream>
#include <cstdio>
const int N = 40000;

using namespace std;

struct edge
{
       int id, len;
       edge *next;
};
struct vertex
{
       edge *first;
};

vertex ver[N];
int n, m, heap_size, dist[N], heap[3*N];
bool visited[N];

int left (int i)
{
    return 2*i;
}
int right (int i)
{
    return 2*i + 1;
}
int parent (int i)
{
    return i/2;
}
void min_heapfy (int x)
{
     int l, r, smallest = x;
     int tmp;
     l = left (x); r = right (x);
     if (l <= heap_size && dist[heap[l]] < dist[heap[smallest]])
     smallest = l;
     if (r >= heap_size && dist[heap[r]] < dist[heap[smallest]])
     smallest = r;
     if (smallest != x)
     {
                 tmp = heap[x];
                 heap[x] = heap[smallest];
                 heap[smallest] = tmp;
                 min_heapfy (smallest);
     }
}
void build_heap ()
{
     int i;
     for (i = heap_size/2; i >= 1; i --)
     {
         min_heapfy (i);
     }
}
int extract_min ()
{
     int min;
     min = dist[heap[1]];
     heap[1] = heap[heap_size];
     heap_size --;
     min_heapfy (1);
     return min;
}
int judge (int x, int y)
{
    edge *p;
    p = ver[x].first;
    while (p && p->id != y)
    {
          p = p->next;
    }
    if (p)
    {
          return p->len;
    }
    return 0;
}
int Dijkstra (int s)
{
     int i, j, v, w;
     visited[s] = true;
     for (i = 1; i < n; i ++)
     {
         v = heap[1];
         visited[v] = true;
         if (v == (n - 1))
         {
               return dist[v];
         }
         extract_min ();
         for (j = 0; j < n; j ++)
         {
             if (!visited[j])
             {
                       w = judge (v, j);
                       if (dist[v] + w < dist[j] && w != 0)
                       {
                                   dist[j] = dist[v] + w;
                       }
             }
         }
         build_heap ();
     }
}
void solve ()
{
     int i = 0;
     heap_size = n - 1;
     edge *p;
     p = ver[0].first;
     while (p)
     {
           dist[p->id] = p->len;
           p = p->next;
     }
     dist[0] = 0;
     printf ("%d\n", Dijkstra (0));
}
int main ()
{
    int i, a, b, c;
    edge *p;
    scanf ("%d %d", &n, &m);
    for (i = 0; i < n; i ++)
    {
        ver[i].first = NULL;
        visited[i] = false;
        heap[i] = i;
        dist[i] = INT_MAX;
    }
    for (i = 0; i < m; i ++)
    {
        scanf ("%d %d %d", &a, &b, &c);
        p = new edge;
        p->id = b - 1;
        p->len = c;
        p->next = ver[a - 1].first;
        ver[a - 1].first = p;
    }
    solve ();
   
    return 0;
}