//Accepted    2692 KB    1282 ms
 //差分约束 -->最短路
 //TLE到死，加了输入挂，手写queue
 #include <cstdio>
 #include <cstring>
 #include <iostream>
 #include <queue>
 #include <cmath>
 #include <algorithm>
 using namespace std;
 /**
   * This is a documentation comment block
   * 如果有一天你坚持不下去了，就想想你为什么走到这儿！
   * @authr songt
   */
 ;
 ;
 const int inf = 0x3f3f3f3f;
 struct node
 {
     int u,v,c;
     node(,,):u(u),v(v),c(c)
     {

     }
 }p[imax_e];
 ;
 int head[imax_n];
 int next[imax_e];
 int dis[imax_n];
 bool vis[imax_n];
 int n,m;
 void addEdge(int u,int v,int c)
 {
     //p[e]=node(u,v,c);
     p[e].u=u;
     p[e].v=v;
     p[e].c=c;
     next[e]=head[u];
     head[u]=e++;
 }
 bool relax(int u,int v,int c)
 {
     if (dis[v]>dis[u]+c)
     {
         dis[v]=dis[u]+c;
         return true;
     }
     return false;
 }
 void init()
 {
     memset(head,-,(n+)*]));
     memset(next,-,(n+)*]));
     e=;
 }
 //queue<int > q;
 int q[imax_e];
 int top;
 void spfa(int src)
 {
     //while (!q.empty()) q.pop();
     //memset(vis,0,(n+2)*sizeof(vis[0]));
     ;i<=n;i++)
     {
         dis[i]=inf;
         vis[i]=;
     }
     dis[src]=;
     //q.push(src);
     top=;
     q[]=src;
     vis[src]=true;
     while (top)
     {
         //int pre=q.front();
         //q.pop();
         int pre=q[--top];

         vis[pre]=false;
         ;i=next[i])
         {
             if (relax(pre,p[i].v,p[i].c) && !vis[p[i].v])
             {
                 vis[p[i].v]=true;
                 //q.push(p[i].v);
                 q[top++]=p[i].v;
             }
         }
     }
 }
 /**
  * 读取一个int
  */
 inline int read_int()
 {
     ;
     char tmp;
     while(!isdigit(tmp=getchar()));
     do{
         ret=(ret<<)+(ret<<)+tmp-';
     }while(isdigit(tmp=getchar()));
     return ret;
 }

 int main()
 {
     //while (scanf("%d%d",&n,&m)!=EOF)
     scanf("%d%d",&n,&m);
     {
         init();
         int u,c,v;
         ;i<m;i++)
         {
             u=read_int();
             v=read_int();
             c=read_int();
             addEdge(u,v,c);
         }
         spfa();
         printf("%d\n",dis[n]);
     }
     ;
 }