#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <iostream>
#include <string>
#include <sstream>
#include <vector>
#include <list>
#include <queue>
#include <map>
#include <set>


using namespace std;





// Constants
const int INF = 1000000000;
const int N = 30010;

vector< list< pair<int,int> > > ad;
int dis[N],n;
/*
int Dijkstra()
{
    for(int i=1;i<=n;i++) dis[i] = INF;
    set< pair<int,int> >Q;
    dis[1] = 0;
    Q.insert(make_pair(0,1));

    while(!Q.empty()){
        pair<int,int> top = *Q.begin();
        int v = top.second;
        //printf("%d %d\n",v,top.first);
        Q.erase(Q.begin());

        list< pair<int,int> >::iterator it;
        for(it = ad[v].begin(); it != ad[v].end(); it++){
            int vv = it->first, dd = it->second;
            if(dis[vv] > dd + dis[v]){

                if(dis[vv] != INF) Q.erase(Q.find(make_pair(dis[vv],vv)));

                dis[vv] = dd + dis[v];
                Q.insert(make_pair(dis[vv],vv));
            }
        }
    }
    return dis[n];
}*/

int Dijkstra()
{
    priority_queue< pair<int,int> > Q;

    for(int i = 1; i <= n; i++) dis[i] = INF;
    dis[1] = 0;
    Q.push(make_pair(0,1));

    while(!Q.empty()){
        pair<int,int> top = Q.top();
        Q.pop();
        int v = top.second, d = - top.first;
        if(d<=dis[v]){
            list< pair<int,int> >::iterator it;
            for(it = ad[v].begin(); it != ad[v].end(); it++){
                int vv = it->first, dd = it->second;
                if(dis[v] + dd < dis[vv]){
                    dis[vv] = dis[v] + dd;
                    Q.push(make_pair(-dis[vv],vv));
                }
            }
        }
    }
    return dis[n];
}



int main()
{
    int i,j,k,m;

   

    scanf("%d%d",&n,&m);
    ad.resize(n+1);
    for(;m;m--){
        scanf("%d%d%d",&i,&j,&k);
        ad[i].push_back(make_pair(j,k));
    }

    printf("%d\n",Dijkstra());

    return 0;
}