#include "bits/stdc++.h"
using namespace std;
#ifdef _DEBUG
#include "dump.hpp"
#else
#define dump(...)
#endif

//#define int long long
#define rep(i,a,b) for(int i=(a);i<(b);i++)
#define rrep(i,a,b) for(int i=(b)-1;i>=(a);i--)
#define all(c) begin(c),end(c)
const int INF = sizeof(int) == sizeof(long long) ? 0x3f3f3f3f3f3f3f3fLL : 0x3f3f3f3f;
const int MOD = (int)(1e9) + 7;
template<class T> bool chmax(T &a, const T &b) { if (a < b) { a = b; return true; } return false; }
template<class T> bool chmin(T &a, const T &b) { if (b < a) { a = b; return true; } return false; }

using Weight = int;
using Flow = int;
struct Edge {
	int s, d; Weight w; Flow c;
	Edge() {};
	Edge(int s, int d, Weight w = 1) : s(s), d(d), w(w), c(w) {};
};
bool operator<(const Edge &e1, const Edge &e2) { return e1.w < e2.w; }
bool operator>(const Edge &e1, const Edge &e2) { return e2 < e1; }
inline ostream &operator<<(ostream &os, const Edge &e) { return (os << '(' << e.s << ", " << e.d << ", " << e.w << ')'); }

using Edges = vector<Edge>;
using Graph = vector<Edges>;
using Array = vector<Weight>;
using Matrix = vector<Array>;

void addArc(Graph &g, int s, int d, Weight w = 1) {
	g[s].emplace_back(s, d, w);
}
void addEdge(Graph &g, int a, int b, Weight w = 1) {
	addArc(g, a, b, w);
	addArc(g, b, a, w);
}

template<typename T>
vector<T> compress(vector<T> v) {
	sort(v.begin(), v.end());
	v.erase(unique(v.begin(), v.end()), v.end());
	return v;
}

template<typename T>
int index(const vector<T> &zip, T i) { return lower_bound(zip.begin(), zip.end(), i) - zip.begin(); }

vector<int> getPath(int s, int g, vector<int> prev) {
	vector<int> path;
	path.emplace_back(g);
	for (int i = g; i != s; ) {
		if (i == -1)
			return vector<int>();
		path.emplace_back(i = prev[i]);
	}
	reverse(path.begin(), path.end());
	return path;
}


signed main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	int N, M; cin >> N >> M;
	using P = tuple<int, int>;
	vector<P> v;
	vector<int> p(M), q(M), c(M); rep(i, 0, M) {
		cin >> p[i] >> q[i] >> c[i];
		p[i]--, q[i]--;
		v.emplace_back(p[i], c[i]);
		v.emplace_back(q[i], c[i]);
	}

	vector<P> zip = compress(v);

	int n = zip.size();
	Graph g(n + N);
	rep(i, 0, M) {
		addEdge(g, index(zip, P(p[i], c[i])), index(zip, P(q[i], c[i])), 0);
	}

	rep(i, 0, n) {
		int cv, cc; tie(cv, cc) = zip[i];
		addEdge(g, n + cv, i, 1);
	}

	auto dijkstra = [&](const Graph &g, int s, Array &dist) {
		int n = g.size();
		vector<bool> vis(n);
		vector<int> prev(n, -1);
		dist.assign(n, INF);
		dist[s] = 0;
		using State = tuple<Weight, int, int>;
		priority_queue<State, vector<State>, greater<State>> pq;
		pq.emplace(0, s, -1);
		while (pq.size()) {
			Weight d; int v, p; tie(d, v, p) = pq.top(); pq.pop();
			if (dist[v] < d)continue;
			vis[v] = true;
			prev[v] = p;
			for (auto &e : g[v]) {
				if (vis[e.d])continue;
				if (dist[e.d] > dist[v] + e.w) {
					dist[e.d] = dist[v] + e.w;
					pq.emplace(dist[e.d], e.d, v);
				}
			}
		}
		return prev;
	};

	// 0-1 BFS 
	auto zeroOneBfs = [&](const Graph &g, int s, Array &dist) {
		int n = g.size();
		deque<int> dq = { s };
		dist.assign(n, INF);
		dist[s] = 0;
		while (dq.size()) {
			int v = dq.front(); dq.pop_front();
			for (auto &e : g[v]) {
				if (dist[e.d] > dist[v] + e.w) {
					dist[e.d] = dist[v] + e.w;
					if (e.w == 0)
						dq.push_front(e.d);
					else
						dq.push_back(e.d);
				}
			}
		}
	};

	Array dist;
	zeroOneBfs(g, n + 0, dist);
	dump(dist);
	cout << (dist[n + N - 1] == INF ? -1 : dist[n + N - 1] / 2) << endl;

	return 0;
}

Measured memory_bytes: 55660