#include <cstdio>
#include <vector>
#include <list>
#include <queue>
#include <utility>
#include <cstring>
#define NMAX 2001
#define inf 2000000
using namespace std;

int n,m;
typedef pair<int,int> pereche;
vector < list < pereche > > Graf;
vector < int > d;
int vizitat[NMAX];
struct order{
    bool operator()(const int &x,const int &y){
        return d[x] > d[y];
    }
};
priority_queue<int,vector<int>,order> Heap;

void citesc(){

    int x,y,c;
    freopen("ubuntzei.in","r",stdin);
    freopen("ubuntzei.out","w",stdout);
    scanf("%d%d",&n,&m);
    Graf.resize(n+1);
    d.resize(n+1,inf);
    for(register int i=1;i<=m;++i){
        scanf("%d%d%d",&x,&y,&c);
        Graf[x].push_back(pereche(y,c));
        Graf[y].push_back(pereche(x,c));
    }
}

int Dijkstra(int nod){

    int top;
    Heap.push(nod);
    vizitat[nod] = 1;
    d[nod] = 0;
        while(!Heap.empty()){
            top = Heap.top();
            Heap.pop();
                for(list < pereche >::iterator it = Graf[top].begin();it!=Graf[top].end();++it){
                    if(d[it->first] > d[top] + it->second)
                         d[it->first] = d[top] + it->second;
                    if(!vizitat[it->first]){
                        vizitat[it->first] = 1;
                        Heap.push(it->first);
                    }
        }}
return d[n];
}

int main(){

    citesc();
    printf("%d",Dijkstra(1));

return 0;
}