#include <bits/stdc++.h>
#define WHOLE(v) (v).begin(), (v).end()
#define REV_WHOLE(v) (v).rbegin(), (v).rend()
using i64 = int64_t;
using namespace std;
template<size_t I,class H,class...T>struct TupleReaderWriter{static tuple<H,T...> r(istream&i){H v;i>>v;return tuple_cat(tuple<H>(v),TupleReaderWriter<sizeof...(T)-1,T...>::r(i));}static void w(ostream&o,tuple<H,T...>&t,string d){TupleReaderWriter<I-1,H,T...>::w(o,t,d);o<<d<<get<I>(t);}};
template<class H,class...T>struct TupleReaderWriter<0,H,T...>{static tuple<H,T...> r(istream&i){H v;i>>v;return tuple<H>(v);}static void w(ostream&o,tuple<H,T...>&t,string d){o<<get<0>(t);}};
template<class...T>istream&operator>>(istream&i,tuple<T...>&t){t=TupleReaderWriter<sizeof...(T),T...>::r(i);return i;}
template<class...T>ostream&operator<<(ostream&o,tuple<T...>&t){string delim=" ";TupleReaderWriter<sizeof...(T)-1,T...>::w(o,t,delim);return o;}
template<class T>istream&operator>>(istream&i,vector<T>&v){for(auto&x:v)i>>x;return i;}
template<class T>ostream&operator<<(ostream&o,vector<T>&v){string delim="";for(auto&x:v)o<<delim<<x,delim=" ";return o;}
template<class T>using rev_priority_queue=priority_queue<T,vector<T>,greater<T>>;
template<class T>using vector2d=vector<vector<T>>;
struct fixprec{int x;fixprec(int d):x(d){}};
ostream&operator<<(ostream&o,fixprec f){return o<<fixed<<setprecision(f.x);}
void R_YESNO(bool p) { cout << (p ? "YES" : "NO") << endl; }
void R_YesNo(bool p) { cout << (p ? "Yes" : "No") << endl; }

/*!* [dijkstra] *!*/
/*+* ダイクストラ法,点sから全ての点への距離をO(V^2)で求める *+*/
template<typename Edge, typename T>
void Dijkstra(const vector<vector<Edge>> &edge, int s, vector<T> &d) {
    using P = pair<T, int>;
    rev_priority_queue<P> q;
    q.push({0, s});
    while(q.size()) {
        T dist;
        int v;
        tie(dist, v) = q.top(); q.pop();
        if(d[v] < dist) continue;
        for(auto&& e : edge[v]) {
            if(d[e.to] > d[v] + e.cost) {
                d[e.to] = d[v] + e.cost;
                q.push({d[e.to], e.to});
            }
        }
    }
}

using P = pair<int, int>;

struct Edge {
    int to, cost;
};

int main() {
    const int INF = 1e8;
    int N, M;
    cin >> N >> M;
    vector2d<P> real_edge(N);
    int K = 0;
    map<P, int> label;
    for(int i = 0; i < M; i++) {
        int p, q, c;
        cin >> p >> q >> c;
        p--, q--;
        real_edge[p].push_back({q, c});
        real_edge[q].push_back({p, c});
    }
    for(int i = 0; i < N; i++) {
        label[{i, 0}] = K++;
        for(P x : real_edge[i]) {
            if(!label.count({i, x.second})) {
                label[{i, x.second}] = K++;
            }
        }
    }
    vector2d<Edge> virtual_edge(K);
    for (int i = 0; i < N; i++) {
        int ex = label[{i, 0}];
        for(P x : real_edge[i]) {
            int cur = label[{i, x.second}];
            int nxt = label[x];
            virtual_edge[ex].push_back({
                cur, 1
            });
            virtual_edge[cur].push_back({
                ex, 0
            });
            virtual_edge[cur].push_back({
                nxt, 0
            });
            virtual_edge[nxt].push_back({
                cur, 0
            });
        }
    }
    vector<int> ans(K, INF);
    ans[0] = 0;
    Dijkstra(virtual_edge, 0, ans);
    int a = ans[label[{N - 1, 0}]];
    if(a >= INF) a = -1;
    cout << a << endl;
    return 0;
}



Measured memory_bytes: 81268