#include  <iostream>
#include  <vector>
#include  <queue>
#include  <cstring>
#define  MAXN  1010
#define  INF  0x3f3f3f3f
using  namespace  std;

struct  Edge  {
        int  v,  w;
        Edge(int  v,  int  w):  v(v),  w(w)  {}
};

vector<Edge>  edges[MAXN];
bool  visited[MAXN];
int  dist[MAXN];

int  dijkstra(int  start,  int  end)  {
        memset(visited,  0,  sizeof(visited));
        memset(dist,  INF,  sizeof(dist));
        dist[start]  =  0;
        priority_queue<pair<int,  int>,  vector<pair<int,  int>>,  greater<>>  pq;
        pq.push(make_pair(dist[start],  start));
        while  (!pq.empty())  {
                auto  p  =  pq.top();
                int  u  =  p.second;
                pq.pop();
                if  (visited[u])  {
                        continue;
                }
                visited[u]  =  true;
                for  (Edge  &e  :  edges[u])  {
                        if  (dist[e.v]  >  dist[u]  +  e.w)  {
                                dist[e.v]  =  dist[u]  +  e.w;
                                pq.push(make_pair(dist[e.v],  e.v));
                        }
                }
        }
        return  dist[end];
}

int  main()  {
        int  n,  m;
        cin  >>  n  >>  m;
        int  u,  v,  w;
        for  (int  i  =  0;  i  <  m;  i++)  {
                cin  >>  u  >>  v  >>  w;
                edges[u].push_back(Edge(v,  w));
        }
        cout  <<  dijkstra(1,  n)  <<  endl;
        return  0;
}