#include <cstdlib>
#include <iostream>
#include <queue>
#include <vector>


using namespace std;

const int MAXn=30010,MAXed=150010,INF=1000000000;

int first[MAXn],next[MAXed],u[MAXed],v[MAXed],w[MAXed],dis[MAXn],edg,n,m;
typedef pair<int,int>pii;
priority_queue< pii,vector<pii>,greater<pii> > q;
void add(int pu,int pv,int pw)
{
    u[edg]=pu;
    v[edg]=pv;
    w[edg]=pw;
    next[edg]=first[pu];
    first[pu]=edg;
    edg++;
}

int dijkstra()
{
    
    int vis[MAXn];
    
    for(int i=1;i<=n;i++)
    {
        vis[i]=0;
        dis[i]=INF;
    }
    dis[1]=0;
    q.push(make_pair(0,1));
    while(!q.empty())
    {
        pii u=q.top();
        q.pop();
        int x=u.second;
        if(vis[x])continue;
        vis[x]=1;
        for(int e=first[x];e!=-1;e=next[e])
        {
            if(dis[v[e]]>dis[x]+w[e])
            {
                dis[v[e]]=dis[x]+w[e];
                q.push(make_pair(dis[v[e]],v[e]));
            }
        }
    }
     return dis[n];
     
}

int main(int argc, char *argv[])
{
    
    edg=0;
    scanf("%d%d",&n,&m);
    memset(first,-1,sizeof(first));
    while(m--)
    {
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c);
        add(a,b,c);
    }
    printf("%d\n",dijkstra());
    //system("PAUSE");
    return EXIT_SUCCESS;
}