#include<bits/stdc++.h>
using namespace std;
#define mp make_pair
#define se second
#define fi first
const int N=2000005;
int n,m,tot,l,x,y,z,f[N],dis[N],to[N],ne[N],fi[N],zz[N],g[N];
vector<pair<int ,int> > G[N];
vector<int> v;
void jb(int x,int y){
	ne[++tot]=fi[x];
	fi[x]=tot;
	zz[tot]=y;
}
int find(int x){
	if (x==f[x])return x;
	return f[x]=find(f[x]);
}
void up(int x){
	if (x==1)return;
	if (dis[f[x]]<dis[f[x/2]]){
		swap(f[x],f[x/2]);
		swap(g[f[x]],g[f[x/2]]);
		up(x/2);
	}
}
void down(int x){
	int i=x;
	if (x*2<=l&&dis[f[x*2]]<dis[f[x]])i=x*2;
	if (x*2<l&&dis[f[x*2+1]]<dis[f[i]])i=x*2+1;
	if (i!=x){
		swap(f[x],f[i]);
		swap(g[f[x]],g[f[i]]);
		down(i);
	}
}
int main(){
	scanf("%d%d",&n,&m);
	while (m--){
		scanf("%d%d%d",&x,&y,&z);
		G[z].push_back(mp(x,y));
	}
	for (int i=1;i<=n;i++)f[i]=i;
	int cnt=n;
	for (int i=1;i<=1000000;i++){
		v.clear();
		for (int j=0;j<G[i].size();j++)f[find(G[i][j].fi)]=find(G[i][j].se);
		for (int j=0;j<G[i].size();j++)v.push_back(G[i][j].fi),v.push_back(G[i][j].se);
		for (int j=0;j<v.size();j++)
			if (find(v[j])==v[j])to[v[j]]=++cnt;
		for (int j=0;j<v.size();j++)jb(to[find(v[j])],v[j]),jb(v[j],to[find(v[j])]);
		for (int j=0;j<v.size();j++)f[v[j]]=v[j];
	}
	dis[1]=0;
	for (int i=2;i<=cnt;i++)dis[i]=1e9;
	for (int i=1;i<=cnt;i++)f[i]=g[i]=i;
	l=cnt;
	for (int i=cnt;i;i--)down(i);
	for (int i=1;i<=cnt;i++){
		int k=f[1];
		f[1]=f[l--];
		g[f[1]]=1;
		down(1);
		for (int j=fi[k];j;j=ne[j])
			if (dis[zz[j]]>dis[k]+1){
				dis[zz[j]]=dis[k]+1;
				up(g[zz[j]]);
			}
	}
	if (dis[n]==1e9)puts("-1");
	else printf("%d\n",dis[n]/2);
	return 0;
}
#include <bits/stdc++.h>
#define enter putchar('\n')
#define space putchar(' ')
#define pb push_back
#define mp make_pair
#define fi first
#define se second
using namespace std;
typedef pair<int, int> pii;
map<pii, int> M;
vector<pii> E[500005];
set<pii> s;
int n, m, ncnt, d[500005];
template <class T> int read(T &x) {
	x = 0; int f = 1; char c = getchar();
	while (c > -1 && c < '0' || c > '9') { if (c == '-') f = -1; c = getchar(); }
	if (c == -1) return 0;
	while (c >= '0' && c <= '9') { x = x * 10 + c - 48; c = getchar(); }
	return x *= f, 1;
}
template <class T> void write(T x) {
	if (x < 0) x = -x, putchar('-');
	if (x > 9) write(x / 10);
	putchar(x % 10 + 48);
}
int main() {
	while (read(n), read(m)) {
		M.clear();
		ncnt = n;
		for (int i = 1; i <= n; ++i)
			E[i].clear();
		for (int i = 1; i <= m; ++i) {
			int u, v, c;
			read(u), read(v), read(c);
			if (!M[mp(u, c)]) {
				M[mp(u, c)] = ++ncnt;
				E[ncnt].clear();
				E[ncnt].pb(mp(u, 1));
				E[u].pb(mp(ncnt, 1));
			}
			if (!M[mp(v, c)]) {
				M[mp(v, c)] = ++ncnt;
				E[ncnt].clear();
				E[ncnt].pb(mp(v, 1));
				E[v].pb(mp(ncnt, 1));
			}
			E[M[mp(u, c)]].pb(mp(M[mp(v, c)], 0));
			E[M[mp(v, c)]].pb(mp(M[mp(u, c)], 0));
		}
		fill(d, d + ncnt + 1, -1);
		d[1] = 0;
		s.insert(mp(d[1], 1));
		while (!s.empty()) {
			int u = s.begin() -> se;
			s.erase(s.begin());
			for (int i = 0; i < E[u].size(); ++i) {
				int v = E[u][i].fi;
				if (d[v] > d[u] + E[u][i].se || d[v] == -1) {
					s.erase(mp(d[v], v));
					d[v] = d[u] + E[u][i].se;
					s.insert(mp(d[v], v));
				}
			}
		}
		write(d[n] >> 1), enter;
	}
	return 0;
}