#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;

template <typename T = double>
using point = complex<T>; // 2D point only

using ll = long long;
using ull = unsigned long long;
using ldob = long double;

template <typename T = int>
using ii = pair<T,T>;
template <typename T = int>
using iii = pair<T,ii<T>>;
template <typename T = int>
using ii_i = pair<ii<T>,T>;
template <typename T = int>
using vi = vector<T>;
template <typename T = int>
using vvi = vector<vi<T>>;
template <typename T = int>
using vii = vector<ii<T>>;
template <typename T = int>
using viii = vector<iii<T>>;
template <typename T = int>
using lim = numeric_limits<T>;

#define re real()
#define im imag()
#define fi first
#define se second
#define sz(v) (v).size()
#define all(v) (v).begin(), (v).end()
#define rall(v) (v).rbegin(), (v).rend()

// OST
template <typename T>
using ordered_set = __gnu_pbds::tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

// from: https://codeforces.com/blog/entry/62393
// struct custom_hash {
// 	static uint64_t splitmix64(uint64_t x) {
// 		// http://xorshift.di.unimi.it/splitmix64.c
// 		x += 0x9e3779b97f4a7c15;
// 		x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
// 		x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
// 		return x ^ (x >> 31);
// 	}

// 	size_t operator()(uint64_t x) const {
// 		static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
// 		return splitmix64(x + FIXED_RANDOM);
// 	}
// };

const int INF = ~(1<<31);
const ll LINF = (1LL << 60);
const long double EPS = 1e-9;
const long double PI = acos(-1);

const int N = 600005;
const int NN = 55;
const int MOD = 1e9+7;
const int IMAX = 1e9+7;
const ll LMAX = 1e15+7;
const int dx[4] = {0,0,-1,1};
const int dy[4] = {-1,1,0,0};
const int dx8[8] = {-1,-1,-1,0,0,1,1,1};
const int dy8[8] = {-1,0,1,-1,1,-1,0,1};

vector<pair<int,int>> adj[N];
map<pair<int,int>,int> id;
int cnt, dist[N];

void add_edge(int u, int v, int w, int w2) {
	adj[u].push_back({v,w}); // going to
	adj[v].push_back({u,w2}); // going back
}

int get_id(int x, int c) {
	if (id.count({x,c}))
		return id[{x,c}];
	id[{x,c}] = cnt++;
	return id[{x,c}];
}

void dijkstra(int s) {
	for (int u = 0; u < cnt; ++u)
		dist[u] = N;
	dist[s] = 0;
	priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> pq;
	pq.push({0,s});
	int u, d, v, w;
	while (not pq.empty()) {
		tie(d,u) = pq.top(); pq.pop();
		if (dist[u] < d)
			continue;
		for (auto &e : adj[u]) {
			tie(v,w) = e;
			if (dist[v] > dist[u] + w) {
				dist[v] = dist[u] + w;
				pq.push({dist[v], v});
			}
		}
	}
}

void solution() {
	int n, m; cin >> n >> m;
	cnt = n;
	for (int i = 0; i < m; ++i) {
		int u, v, c; cin >> u >> v >> c;
		u--; v--;
		
		int nu = get_id(u, c), nv = get_id(v, c);
		add_edge(nu,nv,0,0);
		add_edge(u,nu,1,0);
		add_edge(v,nv,1,0);
	}

	dijkstra(0);

	int ans = N;
	for (auto &e : id)
		if (e.fi.fi == n-1)
			ans = min(ans, dist[e.se]);
	cout << (ans == N ? -1 : ans) << endl;
}

int main () {
	ios_base::sync_with_stdio(false); cin.tie(0); // cout.tie(0);
	// cout.precision(2); cout << fixed;

	int T = 1;
	// cin >> T;
	for (int i = 1; i <= T; ++i) {
		solution();
	}

	return 0;
}

Measured memory_bytes: 64364