#include <bits/stdc++.h>
using namespace std;

#define pb push_back
#define mp make_pair
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef complex<double> point;
#define xx real()
#define yy imag()

#define REP(i, a, b) for(int i = (a); i < (int)(b); i++)
#define REPN(i, a, b) for(int i = (a); i <= (int)(b); i++)
#define FA(it, x) for(__typeof((x).begin()) it = (x).begin(); it != (x).end(); it++)
#define SZ(x) (int)(x).size()
#define BE(x) (x).begin(), (x).end()
#define SORT(x) sort(BE(x))
#define _1 first
#define _2 second

#define x1 gray_cat_x1
#define y1 gray_cat_y1

template<class T> T gcd(T a, T b) { return b ? gcd(b, a % b) : a; }

#define file "cycle"

const double EPS = 1e-9;
const double PI = acos(-1.);
const int INF = 1e9;
const ll MOD = 1e9 + 7;

const int MAXN = 1e5 + 5, MAXE = 4e5 + 5;

struct edge{
	int s, to, c;
	edge(){}
	edge(int _s, int _to, int _c){
		s = _s, to = _to, c = _c;
	}
};

struct graph {
	// Number of vertices and edges
	int n, m;
	
	// Edges (ind, ind ^ 1 - the same edge in different directions)
	edge ee[MAXE];
	
	// Graph
	vi g[MAXN];
	
	// minimal distances
	int dis[MAXE];
	
	int dis_v[MAXN];
	
	int used[MAXN];
	
	// Set for dijkstra
	set<pii> st;
	
	map<pii, vi> inds;
	
	set<pii> used_c;
	
	// Adding edge
	void add_edge(int a, int b, int c, int ee_ind){
		ee[2 * ee_ind] = edge(a, b, c);
		ee[2 * ee_ind + 1] = edge(b, a, c);
		g[a].pb(2 * ee_ind);
		g[b].pb(2 * ee_ind + 1);
		inds[mp(a, c)].pb(2 * ee_ind);
		inds[mp(b, c)].pb(2 * ee_ind + 1);
	}
	
	void upd_dis_by_edge(int cur_e, int to, int c, int ind){
		int add = (c == ee[ind].c ? 0 : 1);
		if (dis[ind] > dis[cur_e] + add){
			st.erase(mp(dis[ind], ind));
			dis[ind] = dis[cur_e] + add;
			st.insert(mp(dis[ind], ind));
			
			dis_v[ee[ind].to] = min(dis_v[ee[ind].to], dis_v[to] + add);
		}
	}
	
	void dijkstra(int s){
		// Init distances, prv
		REP(i, 0, 2 * m){
			dis[i] = INF;
		}
		REPN(i, 1, n){
			dis_v[i] = INF;
			used[i] = 0;
		}
		REP(i, 0, SZ(g[s])){
			int ind = g[s][i];
			dis[ind] = 1;
			dis_v[ee[ind].to] = 1;
			used_c.insert(mp(s, ee[ind].c));
		}
		dis_v[s] = 0;
		used[s] = 1;
		
		
		// Init set
		st.clear();
		REP(i, 0, 2 * m){
			st.insert(mp(dis[i], i));
		}
		
		// Go
		while(!st.empty()){
			int cur_e = st.begin()->second;
			int to = ee[cur_e].to;
			int c = ee[cur_e].c;
			st.erase(st.begin());
			
			if (dis_v[to] < dis[cur_e]){
				continue;
			}
			
			vi &vv = g[to];
			
			if (!used[to]){
				used[to] = 1;				
			} else {
				if (used_c.find(mp(to, c)) != used_c.end()){
					continue;
				}
				used_c.insert(mp(to, c));
				vv = inds[mp(to, c)];
			}
			
			REP(i, 0, SZ(vv)){
				int ind = vv[i];
				upd_dis_by_edge(cur_e, to, c, ind);
			}
			
			
		}		
	}
} gg;


void solve(){
	scanf("%d%d", &gg.n, &gg.m);
	REP(i, 0, gg.m){
		int a, b, c;
		scanf("%d%d%d", &a, &b, &c);
		gg.add_edge(a, b, c, i);
	}
	gg.dijkstra(1);
	int ans = INF;
	REP(i, 0, 2 * gg.m){
		//printf("%d %d %d %d\n", gg.ee[i].s, gg.ee[i].to, gg.ee[i].c, gg.dis[i]);
		if (gg.ee[i].to == gg.n){
			ans = min(ans, gg.dis[i]);
		}
	}
	if (ans == INF){
		ans = -1;
	}
	printf("%d\n", ans);
}	

int main(){

	//freopen(file".in", "r", stdin); freopen(file".out", "w", stdout);
	int t = 1;
	//cin >> t;
	while(t--){
		solve();	
	}
}

Measured memory_bytes: 76544