#include<bits/stdc++.h>
#define ALL(c) (c).begin(),(c).end()
#define EACH(i,c) for(auto i=(c).begin();i!=(c).end();++i)
using namespace std;
#define int long long

const int INF = (int)1e17;

typedef int Weight;
struct Edge{
    int from, to;
    Weight weight;
    int rev;     // ネットワークフロー時の逆辺
    Edge(int from, int to, Weight weight) :
        from(from), to(to), weight(weight) { }
    Edge(int from, int to, Weight weight, int rev) :
        from(from), to(to), weight(weight), rev(rev){ }
};
bool operator < (const Edge &a, const Edge &b){
    if(a.weight != b.weight) return a.weight > b.weight;
    if(a.from != b.from) return a.from > b.from;
    return  a.to > b.to;
}
typedef vector<Edge> Edges;
typedef vector<Edges> Graph;

typedef vector<Weight> Array;
typedef vector<Array> Matrix;

void addFlowEdge(Graph &g, int a, int b, Weight c){
    g[a].push_back(Edge(a, b, c, g[b].size()));
    g[b].push_back(Edge(b, a, 0, g[a].size() - 1));
}
void addUndirectedEdge(Graph &g, int a, int b, Weight c){
    g[a].push_back(Edge(a, b, c, g[b].size()));
    g[b].push_back(Edge(b, a, c, g[a].size() - 1));
}

void dijkstra(const Graph &g, int s, vector<Weight> &dist, vector<int> &prev){
    int n = g.size();
    dist.assign(n, INF);
    dist[s] = 0;
    prev.assign(n, -1);
    priority_queue<Edge> Q;     // a < b <-> a.weight > b.weight
    Q.push(Edge(-2, s, 0));
    while(!Q.empty()){
        Edge e = Q.top(); Q.pop();
        if(prev[e.to] != -1) continue;
        prev[e.to] = e.from;
        EACH(i, g[e.to]){
        //for(Edges::const_iterator i=g[e.to].begin(); i!=g[e.to].end(); ++i){    //マクロが使えないとき
            if(dist[i -> to] > dist[i -> from] + i -> weight){
                dist[i -> to] = dist[i -> from] + i -> weight;
                Q.push(Edge(i -> from, i -> to, dist[i -> to]));
            }
        }
    }
}
vector<int> buildPath(const vector<int> &prev, int t){
    vector<int> path;
    for(int v = t; v >= 0; v = prev[v])
        path.push_back(v);
    reverse(path.begin(), path.end());
    return path;
}

signed main(){
	int N, M;
	cin >> N >> M;
	++N;
	vector<int> p(M), q(M), c(M);
	vector<pair<int,int>> vs;
	for(int i = 0; i < M; ++i) {
		cin >> p[i] >> q[i] >> c[i];
		vs.push_back(make_pair(p[i], c[i]));
		vs.push_back(make_pair(q[i], c[i]));
	}
	for(int i = 0; i < N; ++i ) {
		vs.push_back(make_pair(i, -1));
	}
	sort(ALL(vs));
	vs.erase(unique(ALL(vs)), vs.end());

	Graph g(vs.size());
	for(int i = 0; i < M; ++i) {
		int u = lower_bound(ALL(vs), make_pair(p[i], c[i])) - vs.begin();
		int v = lower_bound(ALL(vs), make_pair(q[i], c[i])) - vs.begin();
		int w = lower_bound(ALL(vs), make_pair(p[i], -1LL)) - vs.begin();
		int x = lower_bound(ALL(vs), make_pair(q[i], -1LL)) - vs.begin();

		addUndirectedEdge(g, u, v, 0);
		g[u].push_back(Edge(u, w, 0));
		g[w].push_back(Edge(w, u, 1));
		g[v].push_back(Edge(v, x, 0));
		g[x].push_back(Edge(x, v, 1));
	}

	int s = lower_bound(ALL(vs), make_pair(1LL, -1LL)) - vs.begin();
	int t = lower_bound(ALL(vs), make_pair(N-1, -1LL)) - vs.begin();
	vector<int> dist(vs.size()), prev(vs.size());
	dijkstra(g, s, dist, prev);

	if(dist[t] == INF) {
		cout << -1 << endl;
	} else {
		cout << dist[t] << endl;
	}
	return 0;
}


Measured memory_bytes: 97640