#include<iostream>
#include<iomanip>
#include<map>
#include<unordered_map>
#include<set>
#include<unordered_set>
#include<vector>
#include<array>
#include<string>
#include<stack>
#include<queue>
#include<algorithm>
#include<cassert>
#include<functional>
#include<random>
#define int int64_t
#define REP(i, a, b) for (int64_t i = (int64_t)(a); i < (int64_t)(b); i++)
#define rep(i, a) REP(i, 0, a)
#define EACH(i, a) for (auto i: a)
#define ITR(x, a) for (auto x = a.begin(); x != a.end(); x++)
#define ALL(a) (a.begin()), (a.end())
#define HAS(a, x) (a.find(x) != a.end())
#define pb(x) push_back(x)
#define mp(x,y) make_pair((x),(y))
using namespace std;

template<typename T>class key_Dijkstra {
	//各頂点が"地名"として型Tの値を持っているグラフ上でダイクストラ法をやる。

public:
	typedef array<int, 2> arr;
	vector<vector<arr>>edges;//arrは[0]が行き先の番号で、[1]が辺の長さ。
	vector<T>name_list;
	map<T, int>index;

	void push_undirected_edge(const T&p1, const T&p2, const int cost) {

		assert(p1 != p2);

		int ip1, ip2;
		if (index.find(p1) == index.end()) {
			index[p1] = ip1 = name_list.size();
			name_list.push_back(p1);
			edges.resize(edges.size() + 1);
		}
		else ip1 = index[p1];
		if (index.find(p2) == index.end()) {
			index[p2] = ip2 = name_list.size();
			name_list.push_back(p2);
			edges.resize(edges.size() + 1);
		}
		else ip2 = index[p2];

		edges[ip1].push_back({ ip2,cost });
		edges[ip2].push_back({ ip1,cost });
	}
	void push_directed_edge(const T&src, const T&dest, const int cost) {

		assert(src != dest);

		int ip1, ip2;
		if (index.find(src) == index.end()) {
			index[src] = ip1 = name_list.size();
			name_list.push_back(src);
			edges.resize(edges.size() + 1);
		}
		else ip1 = index[src];
		if (index.find(dest) == index.end()) {
			index[dest] = ip2 = name_list.size();
			name_list.push_back(dest);
			edges.resize(edges.size() + 1);
		}
		else ip2 = index[dest];

		edges[ip1].push_back({ ip2,cost });
	}
	vector<int>Dijkstra(const T start, const int INF) {
		//返り値はstartから各点への移動コスト。

		//繋ぐ頂点が同じ辺が複数ある場合、コスト最小のもの以外を除く。
		rep(i, edges.size())if(1 <= edges[i].size()){
			sort(ALL(edges[i]));
			vector<arr>E(1,edges[i][0]);
			REP(j, 1, edges[i].size())if (edges[i][j - 1][0] != edges[i][j][0]) {
				E.push_back(edges[i][j]);
			}
			edges[i] = E;
		}

		vector<int>cost(edges.size(), INF);
		auto itr = index.find(start);
		if (itr == index.end())return cost;

		priority_queue<arr, vector<arr>, greater<arr>>D;
		D.push({ 0,index[start] });
		while (!D.empty()) {
			arr a = D.top(); D.pop();
			const int now_cost = a[0];
			const int now_pos = a[1];
			if (cost[now_pos] <= now_cost)continue;
			cost[now_pos] = now_cost;
			for (auto x : edges[now_pos]) {
				const int next_pos = x[0];
				const int next_cost = now_cost + x[1];
				D.push({ next_cost,next_pos });
			}
		}
		return cost;
	}
};

signed main(void) {
	cin.tie(0);
	ios::sync_with_stdio(false);

	int N, M;
	cin >> N >> M;


	key_Dijkstra<array<int, 2>>Dijkstra;
	rep(i, M) {
		int p, q, c;
		cin >> p >> q >> c;
		p--; q--; c--;

		Dijkstra.push_directed_edge({ p,c }, { p,-1 }, 0);
		Dijkstra.push_directed_edge({ p,-1 }, { p,c }, 1);
		Dijkstra.push_directed_edge({ q,c }, { q,-1 }, 0);
		Dijkstra.push_directed_edge({ q,-1 }, { q,c }, 1);

		Dijkstra.push_undirected_edge({ p,c }, { q,c }, 0);
	}

	if (M == 0 || Dijkstra.index.find({ N - 1, -1 }) == Dijkstra.index.end()) {
		cout << -1 << endl;
		return 0;
	}

	const auto costs = Dijkstra.Dijkstra({ 0,-1 }, 99999999);
	const int answer = costs[Dijkstra.index[{N - 1, -1}]];

	if (answer == 99999999)cout << -1 << endl;
	else cout << answer << endl;
}

Measured memory_bytes: 90896