#include <fstream>
#include <cstring>
#include <set>
#include <vector>
#define nmax 2000
#define inf 0x3f3f3f

using namespace std;

vector < int > gf[nmax], c[nmax];
multiset<pair<int,int> >   heap;

int n, m, d[nmax] ;

void dijkstra(){
    memset(d, inf, sizeof(d));
    d[1]=0;
    heap.insert(make_pair(0,1));
    while(heap.size()){
        int min = (*heap.begin()).first;
        int nod = (*heap.begin()).second;
        heap.erase(*heap.begin());
        for(int i=0; i<gf[nod].size(); ++i){
            int vecin = gf[nod][i];
            int cost_act = c[nod][i];
            if (d[ vecin ] > min + cost_act){
                d[ vecin ] = min + cost_act;
                heap.insert(make_pair(d[ vecin ],vecin));
            }
        }
    }

}

int main(){
    ifstream f("ubuntzei.in");
    ofstream g("ubuntzei.out");
    f>>n>>m;

    for(int i=1; i<=m; i++){
        int x, y, cost;
        f>>x>>y>>cost;
        gf[x].push_back(y);
        c[x].push_back(cost);
    }
    dijkstra();
    /*
    for(int i=2; i<=n; i++) if (d[i] >= inf) g<<"0 ";
    else g<<d[i]<<" ";
    */
    g<<d[n];
    return 0;
}