#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <set>
#include <map>
#include <unordered_map>
#include <vector>
#include <queue>
#include <string>
#include <iomanip>
#include <stdio.h>
#include <cstring>
#include <random>
#include <chrono>
#include <bitset>
#include <fstream>
#include <sstream>

using namespace std;

typedef long long ll;
typedef long double ld;

ll big = 1000000007ll;
float likeabutterfly;
string likeabee;
int n,m,q,h,k,w;
ll T;

ll mod(ll i){
if(i < 0)return mod(i+big*big);
if(i < big)return i;
return i%big;
}

ll upp(ll i, ll j){
if(j == 0)return 1;
if(j%2 == 0){
    ll h = upp(i,j/2);
    return mod(h*h);
}
return mod(i*upp(i,j-1));
}

vector<vector<ll> > CI(200001 , vector<ll>());
vector<ll> I;
ll A[200001][2];
ll deg[100001] = {0};
bool emark[200001] = {0};

ll deg2[100001] = {0};
vector<vector<ll> > C(100001 , vector<ll>());


bool comp(ll i, ll j){
return I[i] < I[j];}

ll bs(ll a , ll i){

if(I[CI[a][0]] > i){return deg[a];}
if(I[CI[a][0]] == i){return 0;}
ll l = 0;
ll r = deg[a];
while(l < r-1){
    ll mid = (l+r)/2;
    if(I[CI[a][mid]] < i){l = mid;}
    else{r = mid;}
}
return r;
}

void bfs1(ll i, ll from){

if(emark[i] == 1){return;}

queue<ll> Q;
Q.push(i);
ll farg = I[i];
vector<ll> klar;
set<ll> S;
bool S2[100001] = {0};



while(!Q.empty()){
    ll j = Q.front();
    Q.pop();
    ll a = A[j][0];
    ll b = A[j][1];
    emark[j] = 1;


    ll c = bs(a , farg);
    if(S2[a] == 0){
        klar.push_back(a);
        S2[a] = 1;
    }
    else{c = deg[a];}


    while(c < deg[a]){
        if(I[CI[a][c]] != farg){break;}
        if(emark[CI[a][c]] == 0){
            emark[CI[a][c]] = 1;
            Q.push(CI[a][c]);
        }
        c++;
    }
    c = bs(b , farg);

    if(S2[b] == 0){
        klar.push_back(b);
        S2[b] = 1;
    }
    else{c = deg[a];}

    while(c < deg[b]){
        if(I[CI[b][c]] != farg){break;}
        if(emark[CI[b][c]] == 0){
            emark[CI[b][c]] = 1;
            Q.push(CI[b][c]);
        }
        c++;
    }
}

for(ll c1 = 0; c1 < klar.size(); c1++){
    if(klar[c1] != from){

        deg2[from]++;
        deg2[klar[c1]]++;
        C[from].push_back(klar[c1]);
        C[klar[c1]].push_back(from);

    }
}
return;
}

 ll SP[100001] = {0};

ll bfs2(ll i){


queue<ll> Q;
ll mark[100001] = {0};
Q.push(i);
mark[i] = 1;
ll w = 0;

while(!Q.empty()){
    ll a = Q.front();
    Q.pop();
    for(ll c1 = 0; c1 < deg[a]; c1++){
        bfs1(CI[a][c1] , a);
    }
    for(ll c1 = 0; c1 < deg2[a]; c1++){

        ll b = C[a][c1];
        if(mark[b] == 0){
            mark[b] = 1;
            SP[b] = 1+SP[a];
            Q.push(b);
        }

    }

}

if(SP[n-1] != 0){return SP[n-1];}
else{return -1;}
}


int main()
{
    ll c1,c2,c3,c4,c5,c6;
    int a,b,d,e,g;
    ll x,y,z;
    //freopen("input.txt","r",stdin);
    //freopen("output.txt","w",stdout);



    scanf("%d %d" , &n ,&m);
    for(c1 = 0; c1 < m; c1++){

         scanf("%d %d %d" , &a ,&b ,&d);
        a--;
        b--;

        deg[a]++;
        deg[b]++;
        CI[a].push_back(c1);
        CI[b].push_back(c1);
        A[c1][0] = a;
        A[c1][1] = b;
        I.push_back(d);
    }

    for(c1 = 0; c1 < n; c1++){
        sort(CI[c1].begin() , CI[c1].end() , comp);
    }

    cout << bfs2(0) << "\n";


	return 0;
}


Measured memory_bytes: 27248