#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
#include <tuple>
#include <queue>
#include <string>
#include <map>
#include <utility>
#include <cassert>

const int maxn = 1e5+1;
typedef long long ll;
using namespace std;
vector<pair<int,int>> g[maxn];
vector<pair<int,int>> split[maxn];
vector<pair<int,int>> ng[1000001];
int cnt;
int conv[1000001];
bool used[1000001];
int d[1000001];
vector<pair<int,int>>::iterator get_v(int vert,int color){
    auto it=lower_bound(split[vert].begin(),split[vert].end(),make_pair(color,-1));
    //assert(it!=split[vert].end() && it->first==color);
    return it;
}
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
 //   freopen("input.txt","r",stdin);
    int n;
    cin>>n;
    int m;
    cin>>m;
    for(int i=1; i<=m; ++i){
        int p,q,c;
        cin>>p>>q>>c;
        g[p].push_back(make_pair(q,c));
        g[q].push_back(make_pair(p,c));
    }
    vector<int> changes;
    for(int i=1; i<=n; ++i){
        for(auto it:g[i]){
            changes.push_back(it.second);
            if (!conv[it.second])
                conv[it.second]=++cnt;
        }

        int v=++cnt; //vertex (i,-1)

        for(int el:changes)
            split[i].emplace_back(el,conv[el]);

        split[i].emplace_back(-1,v);
        sort(split[i].begin(),split[i].end());
        split[i].resize(distance(split[i].begin(),unique(split[i].begin(),split[i].end())));

        while(!changes.empty()) {
            conv[changes.back()] = 0;
            changes.pop_back();
        }
    }

//    for(int i=1; i<=n; ++i){
//        for(auto it:split[i])
//            cout<<it.first<<" "<<it.second<<" ";
//        cout<<endl;
//    }
    for(int i=1; i<=n; ++i){
        for(auto it:g[i]){

            int color=it.second;

            auto to = get_v(it.first,color);

            assert(to!=split[it.first].end());

            int non = split[i].front().second;

            assert(split[i].front().first==-1);

            ng[non].emplace_back(to->second,1);
          //  cout<<"edge "<<non<<" "<<to->second<<" "<<1<<endl;
            auto me = get_v(i,color);
            int to_non=split[it.first].front().second;
            if (me!=split[i].end() && me->first==color){
                ng[me->second].emplace_back(to->second,0);
                ng[me->second].emplace_back(to_non,0);
             //   cout<<"edge "<<me->second<<" "<<to->second<<" "<<0<<endl;
             //   cout<<"edge "<<me->second<<" "<<to_non<<" "<<0<<endl;
            }


            ng[non].emplace_back(to_non,1);
         //   cout<<"edge "<<non<<" "<<to_non<<" "<<1<<endl;


        }
    }
    int s=split[1].front().second;
    int t=split[n].front().second;
    deque<int> q;
    for(int i=1; i<=cnt; ++i){
        d[i]=10000000;
    }
    d[s]=0;
    q.push_front(s);

    while(!q.empty()){
        int v=q.front();
        //cout<<"RETRIEVE "<<v<<" "<<d[v]<<endl;
        q.pop_front();
        if (used[v])
            continue;
        used[v]=1;

        for(pair<int,int> to:ng[v]) {
            //cout<<to.first<<endl;
            d[to.first] = min(d[to.first],d[v] + to.second);
            if (to.second)
                q.push_back(to.first);
            else
                q.push_front(to.first);

        }
    }
//
//    for(int i=1; i<=cnt; ++i)
//        cout<<i<<" "<<d[i]<<"\n";
    if (d[t]==10000000)
        cout<<-1;
    else
        cout<<d[t];
}

Measured memory_bytes: 72960