#include <iostream>
#include <climits>
#include <vector>

#define MAX_N   2048         // massimo lato della regione tibetana
#define MAX_DST INT_MAX      // massima distanza possibile

using namespace std;

vector<int> ListaDiAdiacenza[MAX_N];
vector<int> Peso[MAX_N];
int Visitato[MAX_N];         // vettore che segna se il nodo e' stato visitato
int Distanza[MAX_N];         // vettore con tutte le distanze dalla sorgente
int N;


int min( int x, int y )      // funzione che calcola il minimo
{
    return x < y ? x : y;
}

void leggi()
{
    int M, a, b, w;
    
    cin >> N >> M;
    for (int i=0; i<M; i++) {         // leggo il grafo, facendo attenzione che questa volta gli archi hanno un verso solo
        cin >> a >> b >> w;
        a--, b--;
        ListaDiAdiacenza[a].push_back(b);
        ListaDiAdiacenza[b].push_back(a);
        Peso[a].push_back(w);
        Peso[b].push_back(w);
    }
}

void dijkstra(int sorgente)           // procedura che calcola tutte le distanze dalla sorgente con l'algoritmo di Dijkstra
{
    int nmin, dmin, finito;

    Distanza[sorgente]=0;             // imposto la distanza della sorgente a 0, il resto e' gia' a infinito

    finito=0;
    while (!finito) {                       // finche' serve, ripeti:
        nmin=-1;
        dmin=MAX_DST;
        for (int i=0; i<N; i++) {           // cerco il nodo non ancora visitato con Distanza[n] minore: quella distanza e' giusta.
            if (!Visitato[i] && Distanza[i] < dmin) {
                nmin=i;
                dmin=Distanza[i];
            }
        }
        if (nmin==-1) {                     // se sono tutte gia' visitate esco,
            finito=1;
        } else {                            // altrimenti la segno come visitata, e aggiorno le distanze delle caselle adiacenti a questa
            Visitato[nmin]=1;
            for (int i=0; i<ListaDiAdiacenza[nmin].size(); i++) {
                Distanza[ListaDiAdiacenza[nmin][i]] = min( Distanza[ListaDiAdiacenza[nmin][i]], Distanza[nmin]+Peso[nmin][i] );
            }
        }
    }
}


int main()
{
    leggi();

    for (int i=0; i<N; i++) {
        Visitato[i] = 0;
        Distanza[i] = MAX_DST;
    }
    dijkstra(0);                            // calcolo tutte le distanze dall'inizio

    cout << Distanza[N-1] << endl;          // stampo la distanza con la fine
    return 0;
}