#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef unsigned long long ull;

ll conv(int station, int company){
    return station*10000000LL+company;
}

int main(){
    int N,M;
    cin >> N >> M;
    map<ll,vector<ll>> E;
    for(int i=0;i<M;i++){
        int p,q,c;
        cin >> p >> q >> c;
        E[conv(p,c)].push_back(conv(q,c));
        E[conv(p,c)].push_back(conv(p,0));
        E[conv(p,0)].push_back(conv(p,c));
        E[conv(q,c)].push_back(conv(p,c));
        E[conv(q,c)].push_back(conv(q,0));
        E[conv(q,0)].push_back(conv(q,c));
    }

    deque<pair<ll,ll>> Q;
    unordered_set<ll> checked;
    Q.push_back(make_pair(conv(1,0),0));
    while(!Q.empty()){
        auto t=Q.front();
        Q.pop_front();
        if(t.first/10000000LL==N){
            cout << t.second << endl;
            return 0;
        }
        if(checked.count(t.first)>0) continue;
        checked.insert(t.first);
        for(ll x:E[t.first]){
            if(checked.count(x)>0) continue;
            if(t.first%10000000LL==0){
                Q.push_back(make_pair(x,t.second+1));
            }else{
                Q.push_front(make_pair(x,t.second));
            }
        }
    }
    cout << "-1" << endl;
    return 0;
}