#include <iostream>
#include <map>
#include <memory>
// #include "ggraph.hh"

#include <cstdlib>
#include <vector>
#include <list>
#include <map>
#include <iostream>
#include <cassert>
#include <memory>
using namespace std;

using Weight = long long;
class Edge{
public:
	int src,dest;
	Edge(int src, int dest): src(src),dest(dest){};
	virtual Weight get_weight()const {return 1;};
	virtual bool operator<(const Edge& other) const {
		return get_weight() < other.get_weight();
	}
};

class WeightedEdge : public Edge{
public:
	Weight weight;
	WeightedEdge(size_t src, size_t dest,Weight weight): Edge(src,dest),weight(weight){};
	virtual Weight get_weight()const {return weight;};
};

class Graph{
private:
	size_t n;
public:
	Graph(size_t n):n(n),adj_lst(n),rev_adj_lst(n){};
	vector<std::unique_ptr<Edge>> edges;
	vector<vector<Edge*>> adj_lst;
	vector<vector<Edge*>> rev_adj_lst;
	vector<Edge*>& get_outgoing(int index);
	vector<Edge*>& get_incoming(int index);

	virtual void add_edge(unique_ptr<Edge>&& e);
	size_t size()const {return n;};
	void dump_edges();

};

void Graph::add_edge(std::unique_ptr<Edge>&& e){
	adj_lst[e->src].push_back(e.get());
	rev_adj_lst[e->dest].push_back(e.get());
	edges.push_back(move(e));
}

vector<Edge*>& Graph::get_outgoing(int index){
	return adj_lst[index];
}
vector<Edge*>& Graph::get_incoming(int index){
	return rev_adj_lst[index];
}

void Graph::dump_edges() {
	for(auto& edge: edges) {
		cout << edge->src << " -> " << edge->dest << endl;
	}
}


// #include "dijkstra.hh"

// #include "ggraph.hh"

#include <queue>
#include <algorithm>

namespace dijkstra{
	using P = pair<Weight,size_t>;

	Weight inf;
	vector<Weight> d;
	vector<Edge*> pre;
	size_t source;

// |E|*log|V|
	void dijkstra(Graph& g,size_t s){
		inf = numeric_limits<Weight>::max()-1;
		d.assign(g.size(),inf);
		pre.resize(g.size());
		source = s;

		priority_queue<P,vector<P>,greater<P>> que;
		que.push(P(0,source));
		d[source] = 0;

		while(!que.empty()){
			P p = que.top();que.pop();
			size_t v = p.second;
			if(p.first > d[v] )
				continue;
			for(auto e: g.get_outgoing(v)){
				if(d[e->dest] > d[v] + e->get_weight()){
					d[e->dest] = d[v] + e->get_weight();
					que.push(P(d[e->dest],e->dest));
					pre[e->dest] = e;
				}
			}
		}
	}
}





using namespace std;
using P = pair<int,int>;
map<P,int> tov;
int id = 0;

int get_id(){
	return id++;
}

int main(){
	int m,n;
	cin >> n >> m;
	for(int i = 1; i <= n; i++){
		tov[P(i,-1)] = get_id();
	}
	vector<WeightedEdge> edges;

	for(int i = 0; i < m; i++){
		int p,q,c;
		cin >> p >> q >> c;
		if(tov.find(P(p,c)) == tov.end()){
			tov[P(p,c)] = get_id();
			edges.push_back(WeightedEdge(tov[P(p,-1)],tov[P(p,c)],1));
			edges.push_back(WeightedEdge(tov[P(p,c)],tov[P(p,-1)],0));
		}

		if(tov.find(P(q,c)) == tov.end()){
			tov[P(q,c)] = get_id();
			edges.push_back(WeightedEdge(tov[P(q,-1)],tov[P(q,c)],1));
			edges.push_back(WeightedEdge(tov[P(q,c)],tov[P(q,-1)],0));
		}
		edges.push_back(WeightedEdge(tov[P(p,c)],tov[P(q,c)],0));
		edges.push_back(WeightedEdge(tov[P(q,c)],tov[P(p,c)],0));
	}

// 	for(auto& item: tov)
// 		cout << item.first.first << ":" << item.first.second << "=" << item.second << endl;

	Graph g(tov.size());
	for(auto& edge: edges){
		g.add_edge(unique_ptr<WeightedEdge>(new WeightedEdge(edge.src, edge.dest, edge.weight)));
	}
// 	g.dump_edges();

	dijkstra::dijkstra(g,tov[P(1,-1)]);
	auto res = dijkstra::d[tov[P(n,-1)]];
	if(res >= dijkstra::inf)
		cout << -1 << endl;
	else
		cout << res << endl;
}



Measured memory_bytes: 180128