// LUOGU_RID: 155446365
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int maxn=5e6+5,INF=1e16;
int n,m,cnt,s;
struct Edge
{
    int to, w, next;
}edge[maxn];
struct node {
    long long u,d;
    bool operator <(const node& rhs) const {
        return d>rhs.d;
    }
};
int head[maxn];
int dis[maxn],d;
set<int>vis_col[maxn];
bool vis[maxn];
void init()
{
    for(int i=0;i<=n;i++)head[i]=-1,dis[i]=INF;
    cnt=0;
}
void add_edge(int u, int v, int w)
{
    edge[cnt].to = v;
    edge[cnt].w = w; 
    edge[cnt].next = head[u];
    head[u] = cnt++;
}
signed main()
{
    cin>>n>>m;
    init();
	for(int i=1;i<=m;i++)
    {
		int u, v, w;
        cin>>u>>v>> w;
        add_edge(u,v,w);
        add_edge(v,u,w);
    }
    s=1;
    dis[1]=0;
    vis[1]=1;
    priority_queue<node>a;
    a.push((node){s,0});
    while(!a.empty())
    {
    	node fr=a.top();
		a.pop();
		int s=fr.u,d=fr.d;
		if(d!=dis[s])continue;
		vis[s]=false;
    	for(int j=head[s];j!=-1;j=edge[j].next)
    	{
    		int v=edge[j].to,p=(vis_col[s].find(edge[j].w)==vis_col[s].end());
    		if(dis[v]>dis[s]+p)
    		{
    			dis[v]=dis[s]+p;
    			if(!vis[v]){
					a.push((node){v,dis[v]});
					vis[v]=true;
    			}
    			vis_col[v].clear();
    			vis_col[v].insert(edge[j].w);
    		}
    		else if(dis[v]==dis[s]+p)
    		{
    			if((vis_col[v].find(edge[j].w)==vis_col[v].end()))
    			{
	    			if(!vis[v]){
						a.push((node){v,dis[v]});
						vis[v]=true;
	    			}
	     			vis_col[v].insert(edge[j].w);
    			}
    		}
    	}
	}
	if(dis[n]!=INF)cout<<dis[n];
    else cout<<"-1";
	return 0;
}