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

#define FOR(i,l,r) for(int i = (l);i < (r);i++)
#define ALL(x) (x).begin(),(x).end()
template<typename T> void chmax(T& a,const T& b){if(a < b) a = b;}
template<typename T> void chmin(T& a,const T& b){if(b < a) a = b;}
typedef long long ll;

int N,M;
map<int,int> min_cost [100001];
struct state{
	int x,y;
	int cost;
	bool operator>(const state& a) const{
		return this->cost > a.cost;
	}
};
map< int,list<state> > edge [100001];

int dijkstra(int s,int g)
{
	priority_queue< state,vector<state>,greater<state> > pq;
	pq.push(state{s,0,0});

	while(pq.empty() == false){
		int x = pq.top().x,y = pq.top().y;
		int cost = pq.top().cost;
		pq.pop();

		if(x == g){
			return cost;
		}
		if(min_cost [x].count(y) && cost >= min_cost [x] [y]) continue;
		min_cost [x] [y] = cost;

		for(auto&& it : edge [x] [y]){
			pq.push(state{it.x,it.y,cost + it.cost});
		}
	}

	return -1;
}

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

	cin >> N >> M;
	FOR(i,0,M){
		int p,q,c;
		cin >> p >> q >> c;
		edge [p] [c].push_back(state{q,c,0});
		edge [q] [c].push_back(state{p,c,0});
		edge [p] [0].push_back(state{p,c,1});
		edge [p] [c].push_back(state{p,0,0});
		edge [q] [0].push_back(state{q,c,1});
		edge [q] [c].push_back(state{q,0,0});
	}

	int ans = dijkstra(1,N);
	cout << ans << endl;

	return 0;
}
