#include <iostream>
#include <vector>
#include <queue>
#include <string>
#include <unordered_map>
#include <boost/functional/hash.hpp>

using namespace std;

template <typename T> class graph{
    public:
        graph(){
            directed = false;
        }
        graph(bool direct){
            directed = direct;
        }

        void addv(T value){
            if(ns.find(value)==ns.end()){
            int i = v.size();
            vector<pair<int,int> > tem;
            v.push_back(tem);
            ns[value] = i;
            }
        }
        void adde(T v1,T v2,int cost){
            int i = ns[v1], j = ns[v2];
            v[i].push_back(make_pair(j,cost));
        }
        vector<pair<int,int> > operator[](T value){
            return v[ns[value]];
        }
        int size(){
            return v.size();
        }
        bool is_exist(T value){
            return !(ns.find(value) == ns.end());
        }
        bool is_directed(){
            return directed;
        }
        int edge_size(){
            int sum = 0;
            int n = v.size();
            for(int i=0;i<n; i++) sum += v[i].size();
            return directed ? sum : (sum / 2);
        }
        long long int dijkstra(T a, T b){
            // if error return -2, if there isnt the route from a to b return -1, else return the valid minimum distance.
            int n = v.size();
            if(ns.find(a)==ns.end() || ns.find(b)==ns.end()) return -2;
            int aa = ns[a], bb = ns[b];
            priority_queue<pair<long long int,int>,vector<pair<long long int,int> >, greater<pair<long long int, int> > > q;
            vector<bool> c(n);
            for(int i=0;i<n;i++) c[i] = false;
            q.push(make_pair(0,aa));
            long long int cost=0;
            while(!q.empty()){
                cost = q.top().first;
                int curr = q.top().second;
                //cout << curr << " : " << cost << endl;
                q.pop();
                if(curr == bb){c[bb] = true; break;}
                if(!c[curr]){
                    c[curr] = true;
                    for(auto i : v[curr]){
                        if(!c[i.first]) q.push(make_pair(i.second + cost, i.first));
                    }
                }
            }
            if(c[bb]) return cost;
            return -1;
        }        
    private:
        vector<vector<pair<int,int> > > v;
        unordered_map<T,int, boost::hash<T>> ns;
        bool directed;
};


int main(){
    graph<pair<int,int>> g;
    int n,m;
    cin >> n >> m;
    for(int i=0;i<n;i++){
        pair<int,int> v = make_pair(i+1,-1);
        g.addv(v);
    }
    for(int i=0;i<m;i++){
        int p,q,c;
        cin >> p >> q >> c;
        pair<int,int> v1 = make_pair(q,c);
        pair<int,int> v2 = make_pair(p,c);
        if(!g.is_exist(v1)){
            g.addv(v1);
            g.adde(make_pair(q,-1), v1, 1);
            g.adde(v1,make_pair(q,-1), 0);
        }
        if(!g.is_exist(v2)){
            g.addv(v2);
            g.adde(make_pair(p,-1), v2, 1);
            g.adde(v2,make_pair(p,-1), 0);
        }
        g.adde(v1,v2,0);
        g.adde(v2,v1,0);
    }
    cout << g.dijkstra(make_pair(1,-1),make_pair(n,-1)) << endl;
    return 0;
}

Measured memory_bytes: 63900