#include <bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f
const int maxn = 1e6+5;
#define Fill(a,b) memset(a,b,sizeof(a))
int n, m;
struct node {
    int to, next, w;
    bool operator < (const node& a) const {
        return w > a.w;
    }
} e[maxn<<1];
int cnt, head[maxn];
void add(int u, int v, int w) {
    e[cnt] = (node){v, head[u], w};
    head[u] = cnt++;
}
bool vis[maxn];
int dis[maxn];
void dij(int st, int ed) {
    priority_queue<node> q;
    Fill(dis,inf); Fill(vis,0);
    dis[st] = 0;
    q.push((node){st, 0, 0});
    while (!q.empty()) {
        node u = q.top();
        q.pop();
        if(vis[u.to]) continue;
        vis[u.to] = 1;

        for (int i = head[u.to]; ~i; i = e[i].next) {
            int to = e[i].to;
            if (dis[to] > dis[u.to] + e[i].w) {
                dis[to] = dis[u.to] + e[i].w;
                q.push((node){to, 0, dis[to]});
            }
        }
    }
    printf("%d\n", dis[ed] == inf?-1:dis[ed]/2);
}
map<int, int>mp[maxn];
void init() {
    cnt = 0; Fill(head, -1);
    for (int i = 1 ; i <= n ; i ++) {
        mp[i].clear();
    }
}
int getid(int x, int y) {        //判断之前的
    if (!mp[x][y]) mp[x][y] = ++n;
    return mp[x][y];
}
int main() {
    while(~scanf("%d%d", &n, &m)) {
        init(); int ed = n;
        for (int i = 1 ; i <= m ; i ++) {
            int u, v, c;
            scanf("%d%d%d", &u, &v, &c);
            int uc = getid(u, c);            //建立虚点
            int vc = getid(v, c);
            add(uc, vc, 0); add(vc, uc, 0);
            add(u, uc, 1); add(uc, u, 1);
            add(v, vc, 1); add(vc, v, 1);
        }
        dij(1, ed);
    }
}