把同一个公司的连通块连到一个虚点上，然后BFS最短路/2。

#include<bits/stdc++.h>
using namespace std;
const int N=4e5+5;
int n,m,tot;
vector<pair<int,int> > E[N];
vector<int> G[N];
int vis[N],dis[N];
int mp[1000003];
void add(int u,int v){G[u].push_back(v);}
void bfs(int u){
	int last=tot;
	vis[u]=1;
	for(auto to:E[u]){
		int cl=to.second;
		int v=to.first;
		if(mp[cl]<=last)mp[cl]=++tot,add(mp[cl],u),add(u,mp[cl]);
		queue<int> q;
		vis[v]=1;
		q.push(v);
		add(mp[cl],v),add(v,mp[cl]);
		while(q.size()){
			int x=q.front();
			q.pop();
			for(auto t:E[x]){
				if(!vis[t.first]&&t.second==cl){
					vis[t.first]=1;
					add(mp[cl],t.first),add(t.first,mp[cl]);
					q.push(t.first);
				}
			}
		}
	}
}
int main(){
	scanf("%d%d",&n,&m);
	tot=n;
	for(int i=1;i<=m;i++){
		int u,v,c;
		scanf("%d%d%d",&u,&v,&c);
		E[u].push_back({v,c});
		E[v].push_back({u,c});
	}
	for(int i=1;i<=n;i++)if(!vis[i])bfs(i);
	for(int i=1;i<=tot;i++)vis[i]=0,dis[i]=N+999;
	queue<int> Q;
	Q.push(1);
	dis[1]=0;
	vis[1]=1;
	while(Q.size()){
		int u=Q.front();
		Q.pop();
		for(int v:G[u]){
			if(!vis[v]){
				dis[v]=dis[u]+1;
				vis[v]=1;
				Q.push(v);
				if(v==n){
					printf("%d",dis[v]/2);
					return 0; 
				}
			}
		}
	}
	puts("-1");
	return 0;
}