#include<cstdio>
#include<vector>
#include<functional>
#include<cstring>
#include<algorithm>
#include<tuple>
#include<set>
#include<map>
#include<queue>
#include<stack>
using namespace std;

const int MAXN = 100000 + 10;
const int MAXM = 200000 + 10;
const int INF = 2147483647;

int n, m, ncnt;

struct comp{
  bool operator()(const pair<int,int> &a, const pair<int,int> &b)const{
    return a.second > b.second;
  }
};

priority_queue< pair<int,int>, vector<pair<int,int>>, comp> pq;

vector< tuple<int,int,int> > edge;

vector< pair<int,int> > ebc[MAXM];

vector<int> v[MAXN];
bool vis[MAXN];

vector< pair<int, int> > ansv[MAXN*10];
bool ansvis[MAXN*10];
int dis[MAXN*10];

set<int> myset;
map<int,int> mymap;

int main(){

  scanf("%d %d", &n, &m);
  ncnt = n;
  int start = 0;
  int end = ++ncnt;

  for(int i = 0 ; i < m ; i++){
    int x, y, c;
    scanf("%d %d %d", &x, &y, &c);
    edge.push_back(make_tuple(x,y,c));
    myset.insert(c);
  }

  set<int> :: iterator set_itr;
  int cnt = 0;
  for(set_itr = myset.begin() ; set_itr != myset.end() ; set_itr++) {
    mymap[ *set_itr ] = cnt++;
  }

  for(int i = 0 ; i < m ; i++){
    int tmp = get<2>(edge[i]);
    int newPos = mymap[tmp];
    ebc[newPos].push_back(make_pair(get<0>(edge[i]), get<1>(edge[i])));
  }

  for(int i = 0 ; i < cnt ; i++){
    myset.clear();
    int siz = (int)ebc[i].size();
    for(int j = 0 ; j < siz ; j++){
      int p = ebc[i][j].first, q = ebc[i][j].second;
      myset.insert(p);
      myset.insert(q);
      v[q].push_back(p);
      v[p].push_back(q);
    }

    for(set_itr = myset.begin() ; set_itr != myset.end() ; set_itr++) {
      int now = *set_itr;
      if(vis[now]) continue;
      vector<int> pt;
      int type = 0;
      stack<int> s;
      s.push(now);
      vis[now] = true;
      while(!s.empty()){
        int tmp = s.top();
        if(tmp == 1) type |= 1;
        if(tmp == n) type |= 2;
        pt.push_back(tmp);
        s.pop();
        for(int i = 0 ; i < (int)v[tmp].size() ; i++){
          if(!vis[v[tmp][i]]){
            s.push(v[tmp][i]);
            vis[v[tmp][i]] = true;
          }
        }
      }
      int mypoint = ++ncnt;
      if(type & 1) ansv[start].push_back(make_pair(mypoint, 1));
      if(type & 2) ansv[mypoint].push_back(make_pair(end, 0));
      for(int j = 0 ; j < (int)pt.size() ; j++){
        ansv[pt[j]].push_back(make_pair(mypoint, 1));
        ansv[mypoint].push_back(make_pair(pt[j], 0));
      }
    }
    
    for(set_itr = myset.begin() ; set_itr != myset.end() ; set_itr++) {
      int now = *set_itr;
      vis[now] = false;
      v[now].clear();
    }
  }

  for(int i = 1 ; i <= ncnt ; i++) dis[i] = INF;
  pq.push( make_pair(start, 0) );
  while(!pq.empty()) {
    pair<int,int> tp = pq.top();
    pq.pop();
    if(ansvis[tp.first]) continue;
    ansvis[tp.first] = true;
    int x = tp.first;
    for(int i = 0 ; i < (int)ansv[x].size() ; i++){
      if(dis[ ansv[x][i].first ] > dis[x] + ansv[x][i].second){
        dis[ansv[x][i].first] = dis[x] + ansv[x][i].second;
        pq.push(make_pair(ansv[x][i].first, dis[ansv[x][i].first]));
      }
    }
  }

  if(dis[end] == INF) puts("-1");
  else {
    printf("%d\n", dis[end]);
  }

  return 0;
}


Measured memory_bytes: 65584