//This disgusting code is wriiten by Juruo D0zingbear
//Please don't hack me! 0v0 <3
#include <iostream>
#include <sstream>
#include <fstream>
#include <string>
#include <vector>
#include <deque>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <algorithm>
#include <functional>
#include <utility>
#include <bitset>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <cstdio>
#include <cstring>
#include <climits>
#include <string.h>
#include <stdio.h>
#include <assert.h>
#define LL long long
#define all(x) (x).begin(),(x).end()
#define pii pair<int,int>
#define piii pair<int, pii >
#define REP(i,n) for (int (i)=0;(i)<(n);(i)++)
#define vi vector<int>
#define vpi vector< pii >
#define INF 2147483647
#define big 19260817
#define pb push_back
#define mp make_pair
using namespace std;
const int Maxk=1005;
string mul(string a,string b){
	int res[Maxk];
	memset(res,0,sizeof(res));
	reverse(a.begin(),a.end());
	reverse(b.begin(),b.end());
	for (int i=0;i<a.length();i++){
		for (int j=0;j<b.length();j++){
			res[i+j]+=(a[i]-'0')*(b[j]-'0');
		}
	}
	for (int i=0;i<Maxk;i++){
		if (res[i]>=10) {
			res[i+1]+=(res[i]/10);
			res[i]%=10;
		}
	}
	string ret;
	bool flag=false;
	for (int i=Maxk-1;i>=0;i--){
		if (flag || res[i]){
			flag=true;
			ret=ret+(char)(res[i]+'0');
		}
	}
	if (ret=="") ret="0";
	return ret;
}
string add(string a,string b){
	if (a.length()<b.length()) swap(a,b);
	while (a.length()!=b.length()){
		b='0'+b;
	}
	for (int i=a.length()-1;i>=0;i--){
		a[i]+=(b[i]-'0');
		if (a[i]>'9' && i){
			a[i]-=10;
			a[i-1]++;
		}
	}
	if (a[0]>'9'){
		a[0]-=10;
		a='1'+a;
	}
	return a;
}

// cf IO: I64d
// atcoder IO: ｌｌｄ
inline int read()
{
	int x = 0, f = 1; char ch = getchar();
	while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }
	while (ch >= '0' && ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); }
	return x * f;
}
const int Maxn=100005;
const int Maxm=1000005;
map<int,vector<int> > G[Maxm];
vector<int> col[Maxm];
vector<int> ng[Maxm];
bool vis[Maxn];
vector<int> tmp;
void dfs(int x,int cc){
	vis[x]=true;
	tmp.pb(x);
	if (!G[cc].count(x)) return;
	for (int i=0;i<G[cc][x].size();i++){
		int vv=G[cc][x][i];
		if (!vis[vv]) dfs(vv,cc); 
	}
}
int dist[Maxm];
void bfs(int s){
	for (int i=0;i<Maxm;i++) dist[i]=-2;
	queue<int> q;
	dist[s]=0;
	q.push(s);
	while (!q.empty()){
		int x=q.front();
		//cout<<x<<endl;
		q.pop();
		for (int i=0;i<ng[x].size();i++){
			int v=ng[x][i];
			if (dist[v]==-2){
				dist[v]=dist[x]+1;
				q.push(v);
			}
		}
	}
}
int main(){
	int n,m;
	scanf("%d %d",&n,&m);
	for (int i=0;i<m;i++){
		int u,v,c;
		scanf("%d %d %d",&u,&v,&c);
		G[c][u].push_back(v);
		G[c][v].push_back(u);
		col[c].pb(u);
		col[c].pb(v);
	}
	int now=n+1;
	for (int i=0;i<Maxm;i++){
		sort(col[i].begin(),col[i].end());
		col[i].resize(unique(col[i].begin(),col[i].end())-col[i].begin());
		for (int j=0;j<col[i].size();j++){
			vis[col[i][j]]=false;
		}
		for (int j=0;j<col[i].size();j++){
			if (!vis[col[i][j]]){
				tmp.clear();
				dfs(col[i][j],i);
				for (int k=0;k<tmp.size();k++){
					ng[now].push_back(tmp[k]);
					ng[tmp[k]].pb(now);
				}
				now++;
			}
		}
	}
	bfs(1);
	printf("%d\n",dist[n]/2);
	return 0;
}

Measured memory_bytes: 157696