#include<iostream>
#include<cstdio>
#include<cstring>

using namespace std;

int n,m,u,v,w,s,t=0,tot=0,top=0;
int dfn[50001],low[50001],stack[50001],scc[50001];
int heap[50001],dijkstra[50001];
int head[50001],to[200001],data[200001],value[200001];
bool vis[50001];

void tarjan(int now){
    int next;
    dfn[now]=low[now]=++t;
    stack[++top]=now;
    vis[now]=true;
    next=head[now];
    while (next!=0){
        if (dfn[data[next]]==0){
            tarjan(data[next]);
            low[now]=min(low[now],low[data[next]]);
        }
        else
            if (vis[data[next]])
                low[now]=min(low[now],dfn[data[next]]);
        next=to[next];
    }
    if (dfn[now]==low[now]){
        while (stack[top]!=now){
            vis[stack[top]]=false;
            scc[stack[top]]=now;
            top--;
        }
        vis[stack[top]]=false;
        scc[stack[top]]=now;
        top--;
    }
}

void adjust(int now){
    int next=now,minNum=dijkstra[heap[now]];
    if (now*2-1<=s && dijkstra[heap[now*2-1]]<minNum){
        next=now*2-1;
        minNum=dijkstra[heap[now*2-1]];
    }
    if (now*2<=s && dijkstra[heap[now*2]]<minNum){
        next=now*2;
        minNum=dijkstra[heap[now*2]];
    }
    if (now!=next){
        heap[0]=heap[now];
        heap[now]=heap[next];
        heap[next]=heap[0];
        adjust(next);
    }
}

int main(){
    freopen("regexp.in","r",stdin);
    freopen("regexp.out","w",stdout);
    int i,j,now,next;
    bool judge;
    scanf("%d%d",&n,&m);
    for (i=1;i<=m;i++){
        scanf("%d%d%d",&u,&v,&w);
        judge=false;
        next=head[u];
        while (next!=0){
            if (data[next]==v){
                judge=true;
                value[next]=min(value[next],w);
                break;
            }
            next=to[next];
        }
        if (!judge){
            tot++;
            to[tot]=head[u];
            data[tot]=v;
            value[tot]=w;
            head[u]=tot;
        }
    }
    
    memset(vis,false,sizeof(vis));
    for (i=1;i<=n;i++)
        if (dfn[i]==0)
            tarjan(i);
            
    for (i=1;i<=n;i++)
        heap[i]=i;
    memset(dijkstra,63,sizeof(dijkstra));
    dijkstra[1]=0;
    s=n;
    for (i=1;i<=n;i++){
        now=heap[1];
        heap[0]=heap[1];
        heap[1]=heap[s];
        heap[s]=heap[0];
        s--;
        next=head[now];
        while (next!=0){
            if (scc[now]==scc[data[next]])
                value[next]=0;
            dijkstra[data[next]]=min(dijkstra[data[next]],dijkstra[now]+value[next]);
            next=to[next];
        }
        for (j=s/2;j>=1;j--)
            adjust(j);
    }
    printf("%d\n",dijkstra[n]);
    return 0;
}