//=======Includes=======||
#include <bits/stdc++.h>//
#include <iostream>     //     ▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄
#include <cmath>        //       ▄██████████████▄
#include <cstdio>       //     ▄█   AC    ████████
#include <cstring>      //    ▄█▄▄    ▄▄▄▄  ██████
#include <utility>      //   █  ██████  ██████████
#include <cstdlib>      // ▄▄██████▄  ████  ██████
#include <cassert>      //█▄▄▄▄▄▄▄▄█        █████
#include <ctime>        //     █             █████
#include <sstream>      //   ▄██           ▄██████
#include <algorithm>    // ▄████         ▄████████
#include <functional>   //██████        ██████████
#include <numeric>      // ███ █         ███ █████
#include <string>       //     █             █████
#include <vector>       //     █             █████
#include <queue>        //     █             █████
#include <stack>        //     █▄▄▄▄▄▄▄▄▄▄▄▄▄███
#include <map>          //        ███      ███
#include <set>          //      █████    █████
#include <iomanip>      //
#include <cctype>       //
//======================||
#define rep(value_type,start,ends) for(int value_type=start;value_type<ends;value_type++) 
#define per(value_type,start,ends) for(int value_type=ends-1;value_type>=start;value_type--)
#define sf scanf
#define gr getchar
#define pf printf 
#define fi first
#define se second
#define accelerate ios::sync_with_stdio(false)
#define all(type) (type).begin(),(type).end()
#define sz(type) (type).size()
#define pb push_back
#define mp make_pair

 using namespace std;
 typedef long long ll;
 inline ll qmul(ll,ll,ll);
 inline ll qpow_qmul(ll,ll,ll);
 inline ll qpow(ll,ll,ll);
 inline ll gcd(ll,ll);
 const int N=1e5;
 const int INF=0x3f3f3ff;
 typedef pair<int,int> pi;
 
inline char inputchar()
{
    return getchar();
}
inline void inputnum(int &ret)
{
    char ch = inputchar();
    while(ch < '0' || ch > '9')
        ch = inputchar();
    ret = ch - '0';
    ch = inputchar();
    while(ch >= '0' && ch <= '9')
    {
        ret = ret * 10 + ch - '0';
        ch = inputchar();
    }
}
 
 struct mes{
 	int u,val;
 };
 
 int cnt;//虚拟节点起始编号 
 map<pi,int>vi;//虚拟节点映射
 
 vector<mes>g[N*6+10];
 int dis[N*6+10];
 bool book[N*6+10];
  
 void SPFA(int start,int n){
 	int mid;
	book[start] = true;
 	dis[start] = 0;
 	queue<int>q;
 	
 	q.push(start);
 	
 	while(!q.empty()){
 		mid = q.front();
 		q.pop();
 		book[mid] = false;
 		rep(i,0,sz(g[mid])){
 			
 			int pos = g[mid][i].u;
 			
 			if(dis[pos] > dis[mid] + g[mid][i].val){
 				
 				dis[pos] = dis[mid] + g[mid][i].val;
 				
 				if(!book[pos]){
 					book[pos] = true;
 					q.push(pos);
				}
				
			} 
			
		}
	}
 	return ;
 }
 
 inline int getid(int &cnt,pi node){
 	if(vi.find(node)==vi.end()){
 		vi[node] = cnt++;
	}
	return vi[node];
 }

 int main(){
 	int n,m;
 	int x,y,belong;
 	
 	//freopen("D:\\1.in","r",stdin);
 	
 	while(~sf("%d%d",&n,&m)){
 		cnt = n+1;//虚拟节点的起始编号
		
		//初始化 
		vi.clear();
		rep(i,0,n+m*2+100){
			book[i] = false;
			g[i].clear();
			dis[i] = INF;
		} 
		 
		rep(i,0,m){
			//read(x);read(y);read(belong);
			//sf("%d%d%d",&x,&y,&belong);
			inputnum(x);
    		inputnum(y);
    		inputnum(belong);
			//先建虚拟节点和其边再与实点连接
			pi mid;//fisrt 城市编号 second 所属公司编号 
			int num,num1;
			mes tmp;
			mid = mp(x,belong);
			num = getid(cnt,mid);
			
			mid = mp(y,belong);
			num1 = getid(cnt,mid);
			
			//虚拟节点之间 所属同一个公司费用为 0 
			tmp.u = num; tmp.val = 0;
			g[num1].push_back(tmp);
			tmp.u = num1;
			g[num].push_back(tmp);
			
			//实点 与 虚拟点 建立连接  费用就跟上下车收费一个意思 
			tmp.u = num; tmp.val = 1;
			g[x].push_back(tmp);
			tmp.u = x;
			g[num].push_back(tmp);
			
			tmp.u = num1;
			g[y].push_back(tmp);
			tmp.u = y;
			g[num1].push_back(tmp);
		} 
		 
		SPFA(1,cnt);
		
		if(dis[n]==INF) puts("-1");
		else pf("%d\n",dis[n]/2);//上下车收了两次费用  
	
	}
 
	return 0;
 }
 
 inline ll qmul(ll a,ll b,ll mod){
 	ll ans = 0,x = a;
 	while(b){
 		if(b&1){
 			ans += x%mod;
 			ans %= mod; 
		}
		x*=2;
		x%=mod;
		b>>=1;
	}
	return ans%mod;
 }
 
 inline ll qpow_qmul(ll x,ll n,ll mod){
 	ll ans = 1,a = x%mod;
 	while(n){
 		if(n&1){
 			ans=qmul(ans,a,mod);
 			ans%=mod;
		}
		a=qmul(a,a,mod);
		a%=mod;
		n>>=1;
	}
	return ans;
 }
 inline ll qpow(ll x,ll n,ll mod){
 	ll ans = 1,a = x%mod;
 	while(n){
 		if(n&1){
 			ans*=a%mod;
 			ans%=mod;
		}
		a*=a%mod;
		a%=mod;
		n>>=1;
	}
	return ans;
 }
 
 inline ll gcd(ll m,ll n){return n==0?m:gcd(n,m%n);}
 

Measured memory_bytes: 60672