#include<bits/stdc++.h>
#define FOR(a, b, c) for(int a=b; a<=c; a++)
#define maxn 1000005
#define maxm 55
#define hrdg 1000000007
#define zh 16711680
#define inf 2147483647
#define llinf 9223372036854775807
#define ll long long
#define pi acos(-1.0)
#define ls p<<1
#define rs p<<1|1
using namespace std;

int n, m, u, v, c;
int dis[maxn], goal;
bool vis[maxn];
struct Edge{
    int to, nex, val;
    bool operator < (const Edge & rhs) const
    {return val > rhs.val;}
}edge[maxn<<1];
int head[maxn], tot;
void add_edge(int u, int v, int c){edge[tot]={v, head[u], c}; head[u]=tot++;}
map<int, int> Map[maxn];
priority_queue<Edge> q;

inline int read(){
    char c=getchar();long long x=0,f=1;
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
    while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
    return x*f;
}

int getid(int x, int y){
    if (!Map[x][y])
        Map[x][y] = ++n;
    return Map[x][y];
}

void dijsktra(int start, int goal)
{
    for (int i = 1; i <= 10 * n; i++)
        dis[i] = inf;
    dis[start] = 0;
    q.push((Edge){start, 0, 0});
    while (!q.empty())
    {
        Edge k = q.top(); q.pop();
        int now = k.to;
        if (vis[now]) continue;
        vis[now] = 1;
        for (int i= head[now]; i; i = edge[i].nex)
        {
            int to = edge[i].to;
            if (dis[to] > dis[now] + edge[i].val)
            {
                dis[to] = dis[now] + edge[i].val;
                q.push((Edge){to, 0, dis[to]});
            }
        }
    }
    if (dis[goal] == inf)
        puts("-1");
    else
        printf("%d", dis[goal] / 2);
}

int main()
{
    n = read(); m = read();
    goal = n;
    for (int i = 1; i <= n; i++) Map[i].clear();
    for (int i = 1; i <= m; i++)
    {
        u = read(); v = read(); c = read();
        int uc = getid(u, c);
        int vc = getid(v, c);
        add_edge(uc, vc, 0); add_edge(vc, uc, 0);
        add_edge(u, uc, 1); add_edge(v, vc, 1);
        add_edge(uc, u, 1); add_edge(vc, v, 1);
    }
    dijsktra(1, goal);
    return 0;
}

/*
6 7
1 2 1
2 3 2
3 5 3
3 6 3
4 5 3
4 1 2
5 6 1
*/
