#include <bits/stdc++.h>
using namespace std;
#define REP(i, n) for(int i = 0;i < n;i++)
#define REPR(i, n) for(int i = n;i >= 0;i--)
#define FOR(i, m, n) for(int i = m;i < n;i++)
#define fi first
#define se second
#define mp make_pair
#define itrfor(itr,A) for(auto itr = A.begin(); itr !=A.end();itr++)
template <class T> using reversed_priority_queue = priority_queue<T, vector<T>, greater<T> >;
typedef long long llong;
char moji[26]={'a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','q','r','s','t','u','v','w','x','y','z'};
char moji2[26]={'A','B','C','D','E','F','G','H','I','J','K','L','M','N','O','P','Q','R','S','T','U','V','W','X','Y','Z'};
char moji3[10]={'0','1','2','3','4','5','6','7','8','9'};
#define Sort(a) sort(a.begin(),a.end());
#define Reverse(a) reverse(a.begin(),a.end());
#define print(a) cout << a << endl;
#define MOD llong(1e9+7)
#define MAX int(2 * 1e5 +5)
#define debug(x)  cout << #x << " = " << (x) << endl;
#define pi acos(-1.0)
#define int llong
#define INF llong(1e17)
void myprint(int* A,int A_num){
   REP(i,A_num) cout << A[i] << " ";
   cout << endl;
}

signed main(){
    int n,m;
    cin >> n >> m;
    vector<pair<int,int>> oriG[n];
    vector<pair<int,int>> G[2 * m + n + 5];
    map<pair<int,int>,int> pairtov;
    map<int,pair<int,int>> vtopair;
    int p,q,c;
    int id = 0;



    
    REP(i,m){
        cin >> p >> q >> c;
        p --;
        q --;
        oriG[p].push_back(mp(q,c));
        oriG[q].push_back(mp(p,c));
        
        if( pairtov.find(mp(p,c)) == pairtov.end() ){
            vtopair[id] = mp(p,c);
            pairtov[mp(p,c)] = id;
            id ++;
        }
        
        if( pairtov.find(mp(q,c)) == pairtov.end() ){
            vtopair[id] = mp(q,c);
            pairtov[mp(q,c)] = id;
            id ++;
        }
        
        
    }




    
    REP(i,n){
        pairtov[mp(i,-1)] = id;
        vtopair[id] = mp(i,-1);
        id ++;
    }

    REP(i,n){
        itrfor(itr,oriG[i]){
            int from = i;
            int to = itr->fi;
            int kaisya = itr->se;
            int fromid = pairtov[mp(from,kaisya)];
            int toid = pairtov[mp(to,kaisya)];
            G[fromid].push_back( mp(toid,0));
        }
    }
    
    REP(i,id){
        pair<int,int> station = vtopair[i];
        int terminal = pairtov[mp(station.fi,-1)];
        G[i].push_back(mp(terminal,0));
        G[terminal].push_back(mp(i,1));
    }
    


   /*
    REP(i,id){
        itrfor(itr,G[i]){
            cout << vtopair[i].fi << " " << vtopair[i].se << endl;
            cout << vtopair[itr->fi].fi << " " << vtopair[itr->fi].se << endl;
            cout << itr->se << endl;
            cout << endl;
        }
    }
    */
    



    deque<int> Q;
    int distance[id];
    REP(i,id) distance[i] = INF;
    int start = pairtov[mp(0,-1)];
    distance[start] = 0;
    Q.push_front(start );


    while(Q.size()){
        int v = Q.front();
        Q.pop_front();
        itrfor(itr,G[v]){
            int to = itr->fi;
            int w = itr->se;
            if(distance[v] + w < distance[to]){
                distance[to] = distance[v] + w;
                if(w == 1) Q.push_back(to);
                else Q.push_front(to);
            }
        }
    }

    int ans = INF;
    itrfor(itr,oriG[n-1]){
        int tmp = pairtov[ mp(n-1,itr->se)];
        ans = min(ans,distance[tmp]);
    }



    if(ans != INF){
        cout << ans << endl;
    }
    else{
        cout << - 1 << endl;
    }




}

Measured memory_bytes: 129664