#include <bits/stdc++.h>
        using namespace std;
        #ifdef DEBUG
            #define debug(...) printf(__VA_ARGS__)
        #else
            #define debug(...) (void)0
        #endif
        #define mp make_pair
        #define pb push_back
        #define LL long long
        #define pii pair<int,int>
        #define PII pair<long long, long long>
        #define fi first
        #define se second
        #define all(x) (x).begin(),(x).end()
        #define SZ(x) ((int)(x).size())
        const int inf = 0x7fffffff; //beware overflow
        const LL INF = 0x7fffffffffffffff; //beware overflow
        #define mem(x, y) memset(x, (y), sizeof(x) );
        #define IOS ios_base::sync_with_stdio(0); cin.tie(0)
        template<typename A, typename B>
        ostream& operator <<(ostream &s, const pair<A,B> &p) {
             return s<<"("<<p.first<<","<<p.second<<")";
        }
        template<typename T>
        ostream& operator <<(ostream &s, const vector<T> &c) {
            s << "[ ";
            for (auto it : c) s << it << " ";
            s << "]";
            return s;
        }
        template<typename T>
        ostream& operator << (ostream &o, const set<T> &st) {
            o << "{";
            for (auto it=st.begin(); it!=st.end(); it++) o << (it==st.begin() ? "" : ", ") << *it;
            return o << "}";
        }
        template<typename T1, typename T2>
        ostream& operator << (ostream &o, const map<T1, T2> &mp) {
            o << "{";
            for (auto it=mp.begin(); it!=mp.end(); it++) {
                o << (it==mp.begin()?"":", ") << it->fi << ":" << it->se;
            }
            o << "}";
            return o;
        }
        #define maxn 100005
        int n, m;
        struct edge{ int u, v, c; };
        vector<edge> e;
        vector<int> G[maxn];
        int d[maxn];
        set<int> Prev[maxn];
        struct state{
            int d;
            int u;
            bool operator < (const state& rhs) const {
                return mp(d, u) < mp(rhs.d, rhs.u);
            }
        };
        int main() {
            cin>>n>>m;
            for(int i = 0; i < m; i++) {
                int p, q, c;
                scanf("%d %d %d", &p, &q, &c);
                G[p].pb( SZ(e) );
                G[q].pb( SZ(e) );
                e.pb( edge{p, q, c} );
            }
            fill(d, d+1+n, 1e9);
            d[1] = 0;
            priority_queue<state> que;
            que.push( state{ 0,1} );
            while(!que.empty() ) {
                state tp = que.top(); que.pop();
                int u = tp.u;

                if( -tp.d > d[u] ) continue;
                for( int e_ind : G[u] ) {
                   int D = d[u];
                    int v = (e[e_ind].u==u)? e[e_ind].v:e[e_ind].u;
                    int now = D + !Prev[u].count( e[e_ind].c);

                    if( now < d[v] )
                        d[v] = now,
                        Prev[v].clear(),
                        Prev[v].insert(e[e_ind].c),
                        que.push( state{ -d[v], v } );
                    else if (now == d[v])
                        Prev[v].insert( e[e_ind].c ) ;
                }
            }
            if( d[n] == 1e9 ) puts("-1");
            else cout<<d[n]<<endl;
        }


Measured memory_bytes: 23984