# include <bits/stdc++.h>

# define x first    
# define y second
# define mp make_pair
// everything go according to my plan      
# define pb push_back
# define sz(a) (int)(a.size())
# define vec vector         
// shimkenttin kyzdary, dzyn, dzyn, dzyn...
# define y1    Y_U_NO_y1
# define left  Y_U_NO_left
# define right Y_U_NO_right  

using namespace std;

typedef pair <int, int> pii; 
typedef long long ll;
typedef long double ld;

const int Mod = (int)1e9 + 7;
const int MX = 1073741822;
const ll MXLL = 4e18;
const int Sz = 2110111;
// a pinch of soul
inline void Read_rap () {
  ios_base :: sync_with_stdio(0);
  cin.tie(0); cout.tie(0);
}
inline void randomizer3000 () {
  unsigned int seed;
  asm ("rdtsc" : "=A"(seed));
  srand (seed);
}
void files (string problem) {   
  if (fopen ((problem + ".in").c_str(),"r")) {
    freopen ((problem + ".in").c_str(),"r",stdin);
    freopen ((problem + ".out").c_str(),"w",stdout);
  }
}
void localInput(const char in[] = "s") { 
  if (fopen (in, "r")) {
    freopen (in, "r", stdin);
  }
  else
    cerr << "Warning: Input file not found" << endl;
}
const int N = 1e5 + 1;
const int M = 2e5 + 1;    

int n, m;

map <int, vec<int> > l[N];

vec<int> C[N];

int x[M], y[M], c[M];

struct graph {
  int n; 
  vec<pii> g[7*M];
  int d[7*M];
  graph (int n) : n(n) {}
        
  void add_edge (int x, int y, int w) {
    cout << x << ' ' << y << ' ' << w << " :: ";
    g[x].pb ({y, w}); g[y].pb ({x, w});       
  }
  void add1_edge (int x, int y, int w) {
    if (x > 7*M-1) {
      cout << -1;
      exit (0);
    }
    g[x].pb ({y, w});  
  }             
  int bfs (vec<int> &st, vec<int> &f) {

    for (int i = 1; i <= n; i++)
      d[i] = n + 1;
    deque <int> q;    
    for (int s : st) {
      q.push_front (s);
      d[s] = 1;
    }
    while (!q.empty()) {
      int v = q.front();
      q.pop_front();
      for (auto x : g[v]) {
        int to = x.x;
        int w = x.y;
        if (d[v] + w < d[to]) {
          d[to] = d[v] + w;
          if (w)
            q.push_back (to);
          else                    
            q.push_front (to);
        }
      }                  
    }        
    int ans = n+1;         
    for (auto t : f)  
      ans = min (ans, d[t]);
    
    if (ans > n)
      return -1;
    else
      return ans;
  }                                 
};     
                
int main()
{                                  
  # ifdef Local
    //localInput();
  # endif
  Read_rap();
  cin >> n >> m;
  for (int i = 1; i <= m; i++) {
    static int x, y, c; cin >> x >> y >> c;
    l[x][c].pb (i);
    l[y][c].pb (i);
    ::x[i] = x;
    ::y[i] = y;
    ::c[i] = c;
  }
  graph G (m);
  int &nodes = G.n;

  vec<int> pref[N], suff[N], t[N];

  for (int i = 1; i <= n; i++) {      
    pref[i].resize (sz(l[i]));
    suff[i].resize (sz(l[i]));

    int j = 0;

    for (auto x : l[i]) {
      C[i].pb (x.x);       
      int c = ++nodes;
      t[i].pb (c);
      for (int y : x.y)   
        G.add1_edge (c, y, 0);
      
      pref[i][j] = ++nodes;
      G.add1_edge (pref[i][j], c, 0);

      if (j)
        G.add1_edge (pref[i][j], pref[i][j - 1], 0);
      j++;
    }
    for (int k = sz(C[i]) - 1; k >= 0; k--) {
      int clr = C[i][k];
      vec<int> &a = l[i][clr];
      
      int c = t[i][k];
      suff[i][k] = ++nodes;
      G.add1_edge (suff[i][k], c, 0);

      if (k + 1 < sz(C[i]))
        G.add1_edge (suff[i][k], suff[i][k + 1], 0);
    }                           
  }   
  for (int i = 1; i <= ::m; i++) {
    int x = ::x[i];
    int y = ::y[i]; 
    int c = ::c[i];

    int m;
    m = lower_bound (C[x].begin(), C[x].end(), c) - C[x].begin();
          
    G.add1_edge (i, t[x][m], 0);
    
    if (m)
      G.add1_edge (i, pref[x][m - 1], 1);
    
    if (m + 1 < sz(C[x]))
      G.add1_edge (i, suff[x][m + 1], 1);
    
    
    m = lower_bound (C[y].begin(), C[y].end(), c) - C[y].begin();
    G.add1_edge (i, t[y][m], 0);
    
    if (m)
      G.add1_edge (i, pref[y][m - 1], 1);
    
    if (m + 1 < sz(C[y]))
      G.add1_edge (i, suff[y][m + 1], 1);
  }
  vec<int> st, f;                
  for (int i = 1; i <= m; i++) {
    if (x[i] == 1 || y[i] == 1)
      st.pb (i);
    if (x[i] == n || y[i] == n)
      f.pb (i);
  }
  cout << G.bfs (st, f);
  return 0;
}






// Coded by Z..



Measured memory_bytes: 164864