//=======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;
 
 //原题链接https://arc061.contest.atcoder.jp/tasks/arc061_c
//hdu假数据卡超时http://acm.hdu.edu.cn/showproblem.php?pid=6386
/*
题解分析参考https://blog.csdn.net/qq_37656398/article/details/81114646 
http://www.cnblogs.com/LuckyGlass-blog/p/9330160.html
由于在同一家公司的铁路上移动是不花费的，只有在换乘时会花费1日元。我们可以视换乘的花费为点权——当换乘到不同公司时花费1，同一家公司时花费0。

对于这种点权因情况而变化的题，最常见的做法便是拆点。
设节点 u 相连的铁路由 c1，c2，...，cp p个公司修建，
则将节点u拆分为节点 uc1~ucp，点uci表示到达点u的铁路是由公司ci修建的。

若两点u,v被公司c修的铁路相连，
则将 uc 与 vc 连接一条权为0的边——因为在同一家公司的铁路上移动无花费。 
如果只通过公司c的铁路能够从u到v（中途不转到其他公司的铁路），
那么我们就能够从uc花费0日元移动到vc。

如果在节点u要从a公司转到b公司，我们需要通过 ua->u->ub。

如何理解这一过程呢？我们可以把u看成一个站点——你到达u时在公司a的站台上，
然后你需要花费1日元回到站点u，然后通过站点u中转，再花费1日元到达公司b的站台。

就好比上下车一样这里收了两次费用 
但是我们会发现，题目要求是换乘只需要1日元，而我的程序每换乘一次需要2日元，
就会比正确答案大一倍，所以最后要除以2。
*/ 
 
 struct mes{
 	int u,val;
 };
 
 struct heap{
 	int dist;
 	int number;
 	//解释优先级小的 
 	bool operator < (const heap &a)const{
		return dist > a.dist;
	}
 };
 
 int cnt;//虚拟节点起始编号 
 map<pi,int>vi;//虚拟节点映射
 
 vector<mes>g[N*6+10];
 int dis[N*6+10];
 bool book[N*6+10];
  
 void Djikstra_heap(int start,int n){
 	priority_queue<heap>q;
	
	heap temp,ud;
	temp.dist = 0;
	temp.number = start;
	
	q.push(temp);
	
	while(!q.empty()){

		temp = q.top();
		book[temp.number] = true;
		q.pop();

		rep(j,0,sz(g[temp.number])){
			int pos = g[temp.number][j].u;
			if(!book[pos] && dis[pos] > temp.dist + g[temp.number][j].val){
				dis[pos] = temp.dist + g[temp.number][j].val;
				ud.dist = dis[pos];
				ud.number = pos;
				q.push(ud);
			}	
		}	
	}
	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);

			//先建虚拟节点和其边再与实点连接
			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);
		} 
		 
		Djikstra_heap(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: 61436