#include <bits/stdc++.h>

namespace fastIO{
#define BUF_SIZE 100000
#define OUT_SIZE 100000
#define ll long long
  //fread->read
  bool IOerror=0;
  inline char nc(){
    static char buf[BUF_SIZE],*p1=buf+BUF_SIZE,*pend=buf+BUF_SIZE;
    if (p1==pend){
      p1=buf; pend=buf+fread(buf,1,BUF_SIZE,stdin);
      if (pend==p1){IOerror=1;return -1;}
      //{printf("IO error!\n");system("pause");for (;;);exit(0);}
    }
    return *p1++;
  }
  inline bool blank(char ch){return ch==' '||ch=='\n'||ch=='\r'||ch=='\t';}
  inline void read(int &x){
    bool sign=0; char ch=nc(); x=0;
    for (;blank(ch);ch=nc());
    if (IOerror)return;
    if (ch=='-')sign=1,ch=nc();
    for (;ch>='0'&&ch<='9';ch=nc())x=x*10+ch-'0';
    if (sign)x=-x;
  }
  inline void read(ll &x){
    bool sign=0; char ch=nc(); x=0;
    for (;blank(ch);ch=nc());
    if (IOerror)return;
    if (ch=='-')sign=1,ch=nc();
    for (;ch>='0'&&ch<='9';ch=nc())x=x*10+ch-'0';
    if (sign)x=-x;
  }
  inline void read(double &x){
    bool sign=0; char ch=nc(); x=0;
    for (;blank(ch);ch=nc());
    if (IOerror)return;
    if (ch=='-')sign=1,ch=nc();
    for (;ch>='0'&&ch<='9';ch=nc())x=x*10+ch-'0';
    if (ch=='.'){
      double tmp=1; ch=nc();
      for (;ch>='0'&&ch<='9';ch=nc())tmp/=10.0,x+=tmp*(ch-'0');
    }
    if (sign)x=-x;
  }
  inline void read(char *s){
    char ch=nc();
    for (;blank(ch);ch=nc());
    if (IOerror)return;
    for (;!blank(ch)&&!IOerror;ch=nc())*s++=ch;
    *s=0;
  }
  inline void read(char &c){
    for (c=nc();blank(c);c=nc());
    if (IOerror){c=-1;return;}
  }
  //fwrite->write
  struct Ostream_fwrite{
    char *buf,*p1,*pend;
    Ostream_fwrite(){buf=new char[BUF_SIZE];p1=buf;pend=buf+BUF_SIZE;}
    void out(char ch){
      if (p1==pend){
        fwrite(buf,1,BUF_SIZE,stdout);p1=buf;
      }
      *p1++=ch;
    }
    void print(int x){
      static char s[15],*s1;s1=s;
      if (!x)*s1++='0';if (x<0)out('-'),x=-x;
      while(x)*s1++=x%10+'0',x/=10;
      while(s1--!=s)out(*s1);
    }
    void println(int x){
      static char s[15],*s1;s1=s;
      if (!x)*s1++='0';if (x<0)out('-'),x=-x;
      while(x)*s1++=x%10+'0',x/=10;
      while(s1--!=s)out(*s1); out('\n');
    }
    void print(ll x){
      static char s[25],*s1;s1=s;
      if (!x)*s1++='0';if (x<0)out('-'),x=-x;
      while(x)*s1++=x%10+'0',x/=10;
      while(s1--!=s)out(*s1);
    }
    void println(ll x){
      static char s[25],*s1;s1=s;
      if (!x)*s1++='0';if (x<0)out('-'),x=-x;
      while(x)*s1++=x%10+'0',x/=10;
      while(s1--!=s)out(*s1); out('\n');
    }
    void print(double x,int y){
      static ll mul[]={1,10,100,1000,10000,100000,1000000,10000000,100000000,
        1000000000,10000000000LL,100000000000LL,1000000000000LL,10000000000000LL,
        100000000000000LL,1000000000000000LL,10000000000000000LL,100000000000000000LL};
      if (x<-1e-12)out('-'),x=-x;x*=mul[y];
      ll x1=(ll)floor(x); if (x-floor(x)>=0.5)++x1;
      ll x2=x1/mul[y],x3=x1-x2*mul[y]; print(x2);
      if (y>0){out('.'); for (size_t i=1;i<y&&x3*mul[i]<mul[y];out('0'),++i); print(x3);}
    }
    void println(double x,int y){print(x,y);out('\n');}
    void print(char *s){while (*s)out(*s++);}
    void println(char *s){while (*s)out(*s++);out('\n');}
    void flush(){if (p1!=buf){fwrite(buf,1,p1-buf,stdout);p1=buf;}}
    ~Ostream_fwrite(){flush();}
  }Ostream;
  inline void print(int x){Ostream.print(x);}
  inline void println(int x){Ostream.println(x);}
  inline void print(char x){Ostream.out(x);}
  inline void println(char x){Ostream.out(x);Ostream.out('\n');}
  inline void print(ll x){Ostream.print(x);}
  inline void println(ll x){Ostream.println(x);}
  inline void print(double x,int y){Ostream.print(x,y);}
  inline void println(double x,int y){Ostream.println(x,y);}
  inline void print(char *s){Ostream.print(s);}
  inline void println(char *s){Ostream.println(s);}
  inline void println(){Ostream.out('\n');}
  inline void flush(){Ostream.flush();}
#undef ll
#undef OUT_SIZE
#undef BUF_SIZE
};
using namespace fastIO;


using namespace std;

const int N_MAX = 5e5 + 10;
const int M_MAX = 3e6 + 10;
struct Edge {
  int v, w, nxt;
} edge[M_MAX];
int cnt;
int head[N_MAX];
int N, M;
inline void add(int u, int v, int w) {
  edge[cnt].v = v;
  edge[cnt].w = w;
  edge[cnt].nxt = head[u];
  head[u] = cnt++;
}

unordered_map<int, int> has[N_MAX];
int dis[N_MAX];
bitset<N_MAX> vis;

inline void dij(int s) {
  dis[s] = 0;
  vis[s] = 1;
  deque<int> que; que.clear();
  que.push_back(s);
  while (!que.empty()) {
    int u = que.front(); que.pop_front();
    if (u == N) return;
    for (int i = head[u]; ~i; i = edge[i].nxt) {
      int v = edge[i].v, w = edge[i].w;
      if (vis[v]) continue;
      if (dis[v] > dis[u] + w) {
        dis[v] = dis[u] + w;
        if (w) que.push_back(v);
        else que.push_front(v);
        vis[v] = 1;
      }
    }
  }
}
int main() {
  memset(head, 0xff, sizeof(head));
  memset(dis, 0x3f, sizeof(dis));
  while (read(N), read(M), !IOerror) {
    int tot = N;
    cnt = 0;
    for (int i = 1; i <= M; i++) {
      int u, v, c;
      read(u);
      read(v);
      read(c);
      
      int uu, vv;
      if (!has[u].count(c)) {
        has[u][c] = ++tot;
        uu = tot;
        add(uu, u, 1);
        add(u, uu, 0);
      } else {
        uu = has[u][c];
      }
      
      if (!has[v].count(c)) {
        has[v][c] = ++tot;
        vv = tot;
        add(vv, v, 1);
        add(v, vv, 0);
      } else {
        vv = has[v][c];
      }
      
      add(uu, vv, 0);
      add(vv, uu, 0);
    }
    
    
    dij(1);
    if (dis[N] >= 0x3f3f3f3f) {
      println("-1");
    } else {
      println(dis[N]);
    }
    
    for (int i = 1; i <= tot; i++) {
      dis[i] = 0x3f3f3f3f;
      vis[i] = 0;
      head[i] = -1;
    }
    for (int i = 1; i <= N; i++) has[i].clear();
  }
}

Measured memory_bytes: 66816