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

using namespace std;

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

vertex ver[N];
int n, m, heap_size, dist[N], index[N], heap[2*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 swap (int &a, int &b)
{
     int t;
     t = a;
     a = b;
     b = t;
}
void min_heapfy (int x)
{
     int l, r, smallest = x;
     if (x >= 1 && x <= heap_size)
     {
          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)
          {
                       swap (index[heap[x]], index[heap[smallest]]);
                       swap (heap[x], heap[smallest]);
                       min_heapfy (smallest);
          }
     }
}
void build_heap ()
{
     int i;
     for (i = heap_size/2; i >= 1; i --)
     {
         min_heapfy (i);
     }
}
int extract_min ()
{
     int min = 0;
     min = dist[heap[1]];
     heap[1] = heap[heap_size];
     index[heap[heap_size]] = 1;
     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;
    }
    else
    {
        return -1;
    }
}
bool empty ()
{
     return heap_size > 0 ? false : true;
}
void decrease (int i)
{
     int j;
     j = i / 2;
     while (i >= 1 && j < i && dist[heap[i]] < dist[heap[j]])
     {
           swap (index[heap[i]], index[heap[j]]);
           swap (heap[i], heap[j]);
           i = j;
           j = i / 2;
     }
}
int Dijkstra (int s)
{
     int t, tmp1, tmp2, j, v, w;
     visited[s] = true;
     while (!empty())
     {
         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 (w != -1 && dist[v] + w < dist[j])
                       {
                                   dist[j] = dist[v] + w;
                                   decrease (index[j]);
                       }
             }
         }
     }
}
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;
     build_heap ();
     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;
        index[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;
}