#include <bits/stdc++.h>
#define typeof(x) __typeof__(x)
#define int long long int
#define double long double
#define mod(x) ((x % MOD) + MOD) % MOD
#define REP(i,a,b) for(int i=(a);i<(b);++i)
#define RREP(i,a,b) for(int i=(b)-1;i>=(a);--i)
#define ALL(c) (c).begin(),(c).end()
#define RALL(c) (c).rbegin(),(c).rend()
#define SZ(c) (int)((c).size())
#define EACH(i,c) for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); ++i)
#define SORT(c) sort(ALL(c))
#define RSORT(c) sort(RALL(c))
#define LB(c,x) (int)(lower_bound(ALL(c),x)-(c).begin())
#define UB(c,x) (int)(upper_bound(ALL(c),x)-(c).begin())
#define COUNT(c,x) (UB(c,x)-LB(c,x))
#define UNIQUE(c) SORT(c); (c).erase(unique(ALL(c)),(c).end());
#define COPY(c1,c2) copy(ALL(c1),(c2).begin())
#define EXIST(s,e) (s).find(e)!=(s).end()
#define PB push_back
#define MP make_pair
#define vec vector
#define DUMP(x)  cerr << #x << " = " << (x) << endl;
#define NL cerr << endl;

using namespace std;

typedef pair<int,pair<int,int>> P;
struct edge { 
   int from;
   pair<int,int> to;
   int cost; };
bool operator< (const edge &edge1, const edge &edge2){
   return edge1.cost < edge2.cost;
};

const int INF = 1e18;
const int MOD = 1e9+7;

template<typename T> ostream& operator << (ostream& s, const vector<T>& v) {
   s << "[";
   for (int i = 0; i < v.size(); i++) { s << v[i]; if (i < v.size() - 1) s << " "; }
   s << "]";
   return s;
}
template<typename T> ostream& operator << (ostream& s, const set<T>& se) {
   s << "{";
   for (auto i = se.begin(); i != se.end(); ++i) {
      s << *i;
      if (next(i) != se.end()) s << ", ";
   }
   s << "}";
   return s;
}
template<typename T1, typename T2> ostream& operator << (ostream& s, const pair<T1,T2>& p) {
   s << "(" << p.first << "," << p.second << ")";
   return s;
}
template<typename T1, typename T2> ostream& operator << (ostream& s, const map<T1,T2>& m) {
   s << "{";
   for (auto i = m.begin(); i != m.end(); ++i) {
      s << i->first << ":" << i->second;
      if (next(i) != m.end()) s << ", ";
   }
   s << "}";
   return s;
}
ostream& operator << (ostream& s, const edge& e) {
   s << "(" << e.from << "->" << e.to << ": " << e.cost << ")";
   return s;
}

void add_edge0(vec<map<int,vec<edge>>>& G, int u, int v, int com) {
   G[u][com].PB((edge){ u, MP(v, com), 0 });
   G[v][com].PB((edge){ v, MP(u, com), 0 });
}
void add_edge1(vec<map<int,vec<edge>>>& G, int u, int com) {
   G[u][com].PB((edge){ u, MP(u, -1), 0 });
   G[u][-1].PB((edge){ u, MP(u, com), 1 });
}

void dijkstra(vec<map<int,vec<edge>>>& G, map<pair<int,int>,int>& d, int s, int scom)
{
   priority_queue<P, vector<P>, greater<P> > que;
   EACH(i, d) {
      i->second = INF;
   }
   d[MP(s,scom)] = 0;
   que.push(MP(0, MP(s,scom)));
   while(!que.empty()) {
      int temp_cost = que.top().first;
      pair<int,int> from = que.top().second;
      que.pop();
      if (d[from] < temp_cost) continue;
      for (int i = 0; i < G[from.first][from.second].size(); i++) {
         edge e = G[from.first][from.second][i];
         if (d[e.to] > d[from] + e.cost) {
            d[e.to] = d[from] + e.cost;
            que.push(MP(d[e.to], e.to));
         }
      }
   }
}

signed main()
{
   int N, M; cin >> N >> M;
   vec<int> p(M), q(M), c(M);
   REP(i, 0, M) {
      cin >> p[i] >> q[i] >> c[i];
      p[i]--; q[i]--; c[i]--;
   }

   vec<map<int,vec<edge>>> G(N);
   REP(i, 0, M) {
      add_edge0(G, p[i], q[i], c[i]);
   }

   vec<set<int>> coms(N);
   REP(i, 0, M) {
      coms[p[i]].insert(c[i]);
      coms[q[i]].insert(c[i]);
   }

   REP(i, 0, N) {
      EACH(c, coms[i]) {
         add_edge1(G, i, *c);
      }
   }

   map<pair<int,int>,int> d;
   REP(i, 0, N) {
      EACH(j, coms[i]) {
         d[MP(i,*j)] = INF;
      }
      d[MP(i,-1)] = INF;
   }
   dijkstra(G, d, 0, -1);
   if (d[MP(N-1,-1)] == INF) {
      cout << -1 << endl;
   } else {
      cout << d[MP(N-1,-1)] << endl;
   }

   return 0;
}


Measured memory_bytes: 177644