#include<bits/stdc++.h>
using namespace std;
struct node{
    int g=0,head=0;
    int dfn=0,low;
    bool ins=false;
    bool vis=false;
    int dis=(1<<30);
};
struct road{
    int ver,Next=0,val;
};

node f[500001];
road r[4000001];
vector<vector<int>> ans;
stack<int> s;
int num=0,tot=1,scc=0;

void rin(int x,int y,int z){
    tot++;
    r[tot].ver=y;
    r[tot].Next=f[x].head;
    r[x].val=z;
    f[x].head=tot; 
}
void vpush(){
    scc++;
    ans.push_back(vector<int>());
}
void tarjan(int x){
    f[x].dfn=f[x].low=++num;
    s.push(x);f[x].ins=true;
    for(int i=f[x].head;i!=0;i=r[i].Next){
        int y=r[i].ver;
        if(f[y].dfn==0){
            tarjan(y);
            f[x].low=min(f[x].low,f[y].low);            
        }
        else if(f[y].ins) f[x].low=min(f[x].low,f[y].dfn);
    }
    if(f[x].dfn==f[x].low){
        vpush();
        int y;
        do{
            y=s.top();s.pop();
            f[y].ins=false;
            f[y].g=scc;
            ans[scc].push_back(y);
        }while(x!=y);
    }
}
void dijkstra(int st){
    priority_queue<pair<int,int>> q;
    f[st].dis=0;
    q.push(make_pair(0,st));
    while(!q.empty()){
        int x=q.top().second;q.pop();
        if(f[x].vis) continue;
        f[x].vis=true;

        for(int i=f[x].head;i!=0;i=r[i].Next){
            int y=r[i].ver,z=r[i].val;

            if(f[y].dis>f[x].dis+z){
                f[y].dis=f[x].dis+z;
                q.push(make_pair(-f[y].dis,y));
            }
        }
    }
}
int main(){
    ans.push_back(vector<int>());
    int n,m;;
    cin>>n>>m;
    for(int i=1;i<=m;i++){
        int x,y,z;
        cin>>x>>y>>z;
        rin(x,y,z);
    }
    for(int i=1;i<=n;i++)
    if(f[i].dfn==0)
    tarjan(i);
    
    for(int i=1;i<=scc;i++)
    for(int j=0;j<ans[i].size();j++)
    for(int k=f[ans[i][j]].head;k!=0;k=r[k].Next)
    if(f[r[k].ver].g!=i)
    rin(i+n,f[r[k].ver].g+n,r[k].val);
    
    dijkstra(f[1].g+n);
    cout<<f[f[n].g+n].dis;
    
    return 0;
}