#include<bits/stdc++.h>
#include<iostream>
#include<cmath>
#include<vector>
#include<string>
#include<queue>
#include<set>
#include<map>
#include<algorithm>
#include<functional>

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<ll, ll> pll;
typedef pair<ull, ull> pullull;
typedef pair<ll, int> plli;
typedef pair<int, pii> pipii;
typedef vector<vector<int> > mati;
typedef vector<vector<double> > matd;
typedef vector<ll> vll;
typedef vector<vector<ll>> vvll;
typedef vector<vector<vector<ll>>> vvvll;
typedef vector<bool> vb;
typedef vector<vector<bool>> vvb;
typedef vector<vector<vector<bool>>> vvvb;

#define FOR(i,x,y) for(ll i=(ll)x; i<(ll)y; ++i)
#define REP(i,y) FOR(i, 0, y)
#define RFOR(i,x,y) for(ll i=(ll)x; i>=(ll)y; --i)
#define RREP(i,x) RFOR(i, x, 0)

template <typename T>
void vec_print(vector<T> VEC){
  REP(i, VEC.size()){
    cout << VEC[i] << " ";
  }
  cout << "\n";
};

template <typename T>
void mat_print(vector<vector<T> > MAT){
  REP(i, MAT.size()){
    REP(j, MAT[i].size()){
      cout << MAT[i][j] << " ";
    }
    cout << "\n";
  }
};

class HOGE{
  public:
    ll to;
    ll company;
    HOGE(void){
      return;
    };
    HOGE(ll to, ll company){
      this->to = to;
      this->company = company;
    };
    ~HOGE(void){
      return;
    };
};

constexpr int INF = (1<<30);
constexpr ll INFLL = 1LL<<62;
constexpr long double EPS = 1e-12;
constexpr ll MOD = (ll)((1E+9)+7);

class Dijkstra{
  //Dijkstra algorithm
  //calculation time complexity: O(|W| log |V|)
  //useful without negative cost
  private:
    struct edge { ll to, cost; };
    typedef pair<ll, ll> P; //first is the shortest distance, second is the number of vertex

    ll V, E;
    vector<ll> d;
    vector<ll> prev;
    vector<vector<edge> > G;

  public:
    Dijkstra(ll V, vector<ll> From, vector<ll> To, vector<ll> Cost){
      //num of vertex
      this->V = V;
      d.resize(V, INFLL);
      prev.resize(V, -1);
      E = (ll)From.size();
      if(To.size() != E || Cost.size() != E){
        fprintf(stderr, "Sizes are different, %ld %ld %ld\n", From.size(), To.size(), Cost.size());
        exit(0);
      }
      G.resize(V);
      for(ll i=0; i<E; ++i){
        edge tmp_forward = {To[i], Cost[i]};
        G[From[i]].push_back(tmp_forward);
      }
      return;
    };

    ~Dijkstra(void){
      return;
    };

    //calculate shortest path from s vertex to others
    void shortest_path(ll s){
      priority_queue<P, vector<P>, greater<P> > que;
      for(ll i=0; i<V; ++i) d[i] = INFLL;
      d[s] = 0;
      que.push(P(0, s));

      while(!que.empty()){
        P p = que.top(); que.pop();
        ll v = p.second;
        if(d[v] < p.first) continue;
        for(ll i=0; i<G[v].size(); i++){
          edge e = G[v][i];
          if(d[e.to] > d[v] + e.cost){
            d[e.to] = d[v] + e.cost;
            prev[e.to] = v;
            que.push(P(d[e.to], e.to));
          }
        }
      }
      return;
    };

    ll get_distance(ll vertex){
      return d[vertex];
    };

    //shortest path to vertex t
    vector<ll> get_path(ll t){
      vector<ll> path;
      for(; t!=-1; t=prev[t]){
        path.push_back(t);
      }
      reverse(path.begin(), path.end());
      return path;
    };
};

ll N, M;

int main(){
  cin.tie(0); // cut the cin and cout (default, std::flush is performed after std::cin)
  ios::sync_with_stdio(false); // cut the iostream and stdio (DON'T endl; BUT "\n";)

  cin >> N >> M;

  vector<ll> From;
  vector<ll> To;
  vector<ll> Cost;

  vector<set<ll> > Companies(N+1);

  map<pair<ll, ll>, ll> mp;
  ll tmp = 0;

  REP(i, M){
    ll p, q, c;
    cin >> p >> q >> c;
    if(mp.find(make_pair(p, c))==mp.end()){
      mp.emplace(make_pair(p, c), tmp);
      mp[make_pair(p, c)] = tmp;
      tmp++;
    }
    if(mp.find(make_pair(q, c))==mp.end()){
      mp.emplace(make_pair(q, c), tmp);
      tmp++;
    }
    if(mp.find(make_pair(p, 0))==mp.end()){
      mp.emplace(make_pair(p, 0), tmp);
      tmp++;
    }
    if(mp.find(make_pair(q, 0))==mp.end()){
      mp.emplace(make_pair(q, 0), tmp);
      tmp++;
    }

    From.push_back(mp[make_pair(p, c)]);
    To.push_back(mp[make_pair(q, c)]);
    Cost.push_back(0);

    From.push_back(mp[make_pair(q, c)]);
    To.push_back(mp[make_pair(p, c)]);
    Cost.push_back(0);

    From.push_back(mp[make_pair(p, c)]);
    To.push_back(mp[make_pair(p, 0)]);
    Cost.push_back(0);

    From.push_back(mp[make_pair(q, c)]);
    To.push_back(mp[make_pair(q, 0)]);
    Cost.push_back(0);

    if(Companies[p].find(c) == Companies[p].end()){
      Companies[p].emplace(c);
    }
    if(Companies[q].find(c) == Companies[q].end()){
      Companies[q].emplace(c);
    }
  }

  FOR(p, 1, N+1){
    for(auto c : Companies[p]){
      From.push_back(mp[make_pair(p, 0)]);
      To.push_back(mp[make_pair(p, c)]);
      Cost.push_back(1);
    }
  }

  /*
  for(int i=0; i<From.size(); ++i){
    printf("%d %d %d\n", From[i], To[i], Cost[i]);
  }
  */

  Dijkstra D(mp.size(), From, To, Cost);

  if(mp.find(make_pair(1, 0))==mp.end()){
    cout << -1 << "\n";
    return 0;
  }
  D.shortest_path(mp[make_pair(1, 0)]);

  /*
  FOR(p, 1, N+1){
    cout << p << "," << 0 << ":" << D.get_distance(mp[make_pair(p, 0)]) << "\n";
    for(auto c : Companies[p]){
      cout << p << "," << c << ":" << D.get_distance(mp[make_pair(p, c)]) << "\n";
    }
  }
  */

  if(mp.find(make_pair(N, 0))==mp.end()){
    cout << -1 << "\n";
    return 0;
  }
  ll ans = D.get_distance(mp[make_pair(N, 0)]);
  if(ans==INFLL) ans = -1;
  cout << ans << "\n";

  return 0;
}

Measured memory_bytes: 164528