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

#define len(x)  (int((x).size()))
#define append push_back
#define pp make_pair
#define ff(a, b)    for (int a = 0; a < int(b); ++a)
#define kk(n)    ff(k, n)
#define xx(n)    ff(x, n)
#define yy(n)    ff(y, n)
#define ii(n)    ff(i, n)
#define fff(a, b, c) for (int a = int(b); a < int(c); ++a)
#define kkk(a, b) fff(k, a, b)
#define xxx(a, b) fff(x, a, b)
#define yyy(a, b) fff(y, a, b)
#define iii(a, b) fff(i, a, b)
#define bb begin()
#define ee end()
#define uu first
#define vv second
#define all(x)  (x).bb, (x).ee
#define ite(v)   decltype((v).bb)
#define fe(i, v) for(ite(v) i = (v).bb; i != (v).ee; ++i)
#define err(...)    { fprintf(stderr, __VA_ARGS__); fflush(stderr); }
#define zz(array, byte)   memset(array, byte, sizeof(array));

using LL = long long;
using DD = long double;
using pii = pair<int, int>;



const LL  INFLL  = 0x7f7f7f7f7f7f7f7fLL;
const int INFint = 0x7f7f7f7f;  //Works with memset(..).
 
typedef priority_queue< pii, vector<pii>, greater<pii> > small_on_top_pq;
     




int main() {
    ios_base::sync_with_stdio(false);     cin.tie(NULL);
    //cout << '\n';
    cout.precision(16);
    
    int N, M;
    cin >> N >> M;

    vector<vector<int> > companies_at_station(N);
    vector<vector<pii> > al_virtual(N);
    ii (M) {
        int p, q, c;
        cin >> p >> q >> c;
        --p, --q, --c;
        companies_at_station[p].append(c);
        companies_at_station[q].append(c);
        al_virtual[p].append(pp(q, c));
        al_virtual[q].append(pp(p, c));
    }

    vector<vector<pii> > al(N+2*M);

    vector<bool> target(N+2*M, false);

    map<pii, int> stationcompany2index;
    int istation = N;
    ii (len(companies_at_station)) {
        companies_at_station[i].append(-1);
        sort(all(companies_at_station[i]));
        kkk (1, len(companies_at_station[i])) {
            if (companies_at_station[i][k] == companies_at_station[i][k-1])
                continue;
            al[i].append(pp(1, istation));
            al[istation].append(pp(1, i));
            if (i == N-1)
                target[istation] = true;
            stationcompany2index[pp(i, companies_at_station[i][k])] 
                = istation++;
            
        }
    }

    ii (len(al_virtual)) {
        kk (len(al_virtual[i])) {
            al[stationcompany2index[pp(i, al_virtual[i][k].vv)]].append(
                    pp(0, stationcompany2index[al_virtual[i][k]]));
        }
    }

    small_on_top_pq pq;
    vector<bool> visited(istation, false);
    pq.push(pp(1, 0));
    while (len(pq) > 0) {
        pii dist_v = pq.top(); pq.pop();
        //printf("at %d cost %d\n", dist_v.vv, dist_v.uu);
        int v = dist_v.vv;
        if (visited[v])
            continue;
        visited[v] = true;
        if (target[v]) {
            cout << dist_v.uu / 2 << '\n';
            return 0;
        }
        fe (it, al[v]) {
            pii dist_next = *it;
            //printf("Next %d cost %d\n", dist_next.vv, dist_next.uu);
            if (!visited[dist_next.vv])
                pq.push(pp(dist_v.uu + dist_next.uu, dist_next.vv));
        }
    }


    cout << (-1) << '\n';

    


    return 0;
}



Measured memory_bytes: 70904