#include <algorithm>
#include <cassert>
#include <climits>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <deque>
#include <iomanip>
#include <iostream>
#include <limits>
#include <map>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <vector>

#define FOR(i,k,n) for (int (i)=(k); (i)<(n); ++(i))
#define rep(i,n) FOR(i,0,n)
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define fst first
#define snd second
#define all(v) begin(v), end(v)
#define debug(x) cerr<< #x <<": "<<x<<endl
#define debug2(x,y) cerr<< #x <<": "<< x <<", "<< #y <<": "<< y <<endl

using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<vector<int> > vvi;
typedef vector<ll> vll;
typedef vector<vector<ll> > vvll;
typedef vector<char> vc;
typedef vector<vector<char> > vvc;
typedef vector<double> vd;
typedef vector<vector<double> > vvd;
template<class T> using vv=vector<vector< T > >;
typedef deque<int> di;
typedef deque<deque<int> > ddi;
typedef deque<bool> db;
typedef deque<deque<bool> > ddb;

// cout pair
template<typename T1, typename T2> ostream& operator<<(ostream& s, const pair<T1, T2>& p) {
    s << p.first << " " << p.second << "\n"; return s;
}

// cout vector<pair>
template<typename T1, typename T2> ostream& operator<<(ostream& s, const vector<pair<T1, T2> >& vp) {
    int len = vp.size(); s << "\n";
    for (int i = 0; i < len; ++i) { s << vp[i]; }
    s << "\n"; return s;
}

// cout vector
template<typename T> ostream& operator<<(ostream& s, const vector<T>& v) {
    int len = v.size(); s << "\n";
    for (int i = 0; i < len; ++i) {
        s << v[i]; if (i < len - 1) s << "\t";
    }
    s << "\n"; return s;
}

// cout deque
template<typename T> ostream& operator<<(ostream& s, const deque<T>& v) {
    int len = v.size(); s << "\n";
    for (int i = 0; i < len; ++i) {
        s << v[i]; if (i < len - 1) s << "\t";
    }
    s << "\n"; return s;
}

// cout 2-dimentional vector
template<typename T> ostream& operator<<(ostream& s, const vector< vector<T> >& vv) {
    int len = vv.size();
    for (int i = 0; i < len; ++i) { s << vv[i]; }
    return s;
}

// cout 2-dimentional deque
template<typename T> ostream& operator<<(ostream& s, const deque< deque<T> >& vv) {
    int len = vv.size();
    for (int i = 0; i < len; ++i) { s << vv[i]; }
    return s;
}

int main() {
    int n, m;
    cin >> n >> m;
    set<pii> v_;
    vi p(m);
    vi q(m);
    vi c(m);
    rep (i, m) {
        cin >> p[i] >> q[i] >> c[i];
        --p[i]; --q[i]; --c[i];
        v_.insert(mp(p[i], c[i]));
        v_.insert(mp(q[i], c[i]));
    }
    vector<pii> v;
    v.reserve(n + v_.size() + 10);
    for (auto elm : v_) {
        v.eb(elm);
    }
    rep (i, n) {
        v.eb(mp(i, -1));
    }
    int vsize = v.size();
    vector<map<int, int> > node_id(n);
    rep (i, vsize) {
        node_id[v[i].fst][v[i].snd] = i;
    }


    int start = node_id[0][-1];
    int goal = node_id[n-1][-1];

    vv<vi> g(vsize);
    rep (i, m) {
        g[node_id[p[i]][c[i]]].pb({0, node_id[q[i]][c[i]]});
        g[node_id[q[i]][c[i]]].pb({0, node_id[p[i]][c[i]]});
    }
    for (pii elm : v) {
        if (elm.snd == -1) { continue; }
        pii outer = mp(elm.fst, -1);
        g[node_id[elm.fst][elm.snd]].pb({0, node_id[outer.fst][outer.snd]});
        g[node_id[outer.fst][outer.snd]].pb({1, node_id[elm.fst][elm.snd]});
    }

    int inf = (1 << 30);
    vi d(vsize, inf);
    d[start] = 0;
    priority_queue<pii> que;
    que.push(mp(-d[start], start)); // -cost, id
    while (!que.empty()) {
        auto curr = que.top();
        que.pop();
        for (vi elm : g[curr.snd]) {
            int alt = -curr.fst + elm[0];
            if (d[elm[1]] > alt) {
                d[elm[1]] = alt;
                que.push(mp(-alt, elm[1]));
            }
        }
    }

    if (d[goal] == inf) {
        d[goal] = -1;
    }
    printf("%d\n", d[goal]);

    return 0;
}


Measured memory_bytes: 141816