#include <iostream>
#include <vector>
#define INF 987654321
#define TAM 10100
using namespace std;
vector<int> dist(TAM, INF);
//vector<int> pred(TAM, INF);
vector<int> dist_i(TAM, INF);
//vector<int> pred_i(TAM, INF);
void BF(vector<vector<pair<int,int> > > &g, int v);
int main(){
int v, a, from, to, peso;
cin>>v>>a;
vector<vector<pair<int,int> > > g(TAM);
while(a--){
cin>>from>>to>>peso; from--; to--;
g[from].push_back(make_pair(to, peso));
g[to].push_back(make_pair(from, peso));
}
dist[0]=0;
BF(g, v);
int aux=dist[v-1];
if(aux!=INF)
cout<<aux<<endl;
else
cout<<"-1"<<endl;
g.clear(); dist.clear(); dist_i.clear(); //pred.clear(); pred_i.clear();
}
void BF(vector<vector<pair<int,int> > > &g, int v){
for(int k=0; k<v; k++)
for(int i=0; i<v; i++)
if(dist[i]!=INF or dist_i[i]!=INF)
for(int j=0; j<g[i].size(); j++){
int vert=g[i][j].first;
if(dist[vert]>dist_i[i]+g[i][j].second){
dist[vert]=dist_i[i]+g[i][j].second;
//pred[vert]=i;
}
if(dist_i[vert]>dist[i]+g[i][j].second){
dist_i[vert]=dist[i]+g[i][j].second;
//pred_i[vert]=i;
}
}
}
I2luY2x1ZGUgPGlvc3RyZWFtPgojaW5jbHVkZSA8dmVjdG9yPgojZGVmaW5lIElORiA5ODc2NTQzMjEKI2RlZmluZSBUQU0gMTAxMDAKdXNpbmcgbmFtZXNwYWNlIHN0ZDsKCnZlY3RvcjxpbnQ+IGRpc3QoVEFNLCBJTkYpOwovL3ZlY3RvcjxpbnQ+IHByZWQoVEFNLCBJTkYpOwp2ZWN0b3I8aW50PiBkaXN0X2koVEFNLCBJTkYpOwovL3ZlY3RvcjxpbnQ+IHByZWRfaShUQU0sIElORik7Cgp2b2lkIEJGKHZlY3Rvcjx2ZWN0b3I8cGFpcjxpbnQsaW50PiA+ID4gJmcsIGludCB2KTsKCmludCBtYWluKCl7CiAgaW50IHYsIGEsIGZyb20sIHRvLCBwZXNvOwogICAgY2luPj52Pj5hOwogICAgdmVjdG9yPHZlY3RvcjxwYWlyPGludCxpbnQ+ID4gPiBnKFRBTSk7CiAgICB3aGlsZShhLS0pewogICAgICBjaW4+PmZyb20+PnRvPj5wZXNvOyBmcm9tLS07IHRvLS07CiAgICAgIGdbZnJvbV0ucHVzaF9iYWNrKG1ha2VfcGFpcih0bywgcGVzbykpOwogICAgICBnW3RvXS5wdXNoX2JhY2sobWFrZV9wYWlyKGZyb20sIHBlc28pKTsKICAgIH0KICAgIGRpc3RbMF09MDsKICAgIEJGKGcsIHYpOwogICAgaW50IGF1eD1kaXN0W3YtMV07CiAgICBpZihhdXghPUlORikKICAgICAgY291dDw8YXV4PDxlbmRsOwogICAgZWxzZQogICAgICBjb3V0PDwiLTEiPDxlbmRsOwogICAgZy5jbGVhcigpOyBkaXN0LmNsZWFyKCk7IGRpc3RfaS5jbGVhcigpOyAvL3ByZWQuY2xlYXIoKTsgcHJlZF9pLmNsZWFyKCk7Cn0KCnZvaWQgQkYodmVjdG9yPHZlY3RvcjxwYWlyPGludCxpbnQ+ID4gPiAmZywgaW50IHYpewogIGZvcihpbnQgaz0wOyBrPHY7IGsrKykKICAgIGZvcihpbnQgaT0wOyBpPHY7IGkrKykKICAgICAgaWYoZGlzdFtpXSE9SU5GIG9yIGRpc3RfaVtpXSE9SU5GKQogICAgICAgIGZvcihpbnQgaj0wOyBqPGdbaV0uc2l6ZSgpOyBqKyspewogICAgICAgICAgaW50IHZlcnQ9Z1tpXVtqXS5maXJzdDsKICAgICAgICAgIGlmKGRpc3RbdmVydF0+ZGlzdF9pW2ldK2dbaV1bal0uc2Vjb25kKXsKICAgICAgICAgICAgZGlzdFt2ZXJ0XT1kaXN0X2lbaV0rZ1tpXVtqXS5zZWNvbmQ7CiAgICAgICAgICAgIC8vcHJlZFt2ZXJ0XT1pOwogICAgICAgICAgfQogICAgICAgICAgaWYoZGlzdF9pW3ZlcnRdPmRpc3RbaV0rZ1tpXVtqXS5zZWNvbmQpewogICAgICAgICAgICBkaXN0X2lbdmVydF09ZGlzdFtpXStnW2ldW2pdLnNlY29uZDsKICAgICAgICAgICAgLy9wcmVkX2lbdmVydF09aTsKICAgICAgICAgIH0KICAgICAgICB9Cn0=