#include<map>
#include<bitset>
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<string>
#include<stack>
#define REP(i,x,y) for(ll i=x;i<=y;i++)
typedef long long ll;
using namespace std;

ll const MAX = 500005;
ll n, m;

struct edge {
	ll from; ll to; ll comp;
};
edge line[MAX];

struct station {
	ll name; ll comp;
	bool operator<(const station& rhs) const {
		if (name != rhs.name) {
			return name > rhs.name;
		}
		else {
			return comp > rhs.comp;
		}
	}

};
station st[MAX];
ll num_st = 1;
map<station, ll> mp;
vector<ll> G[MAX];
struct point {
	ll name; ll dist;
	
};
bool st_order(station x, station y) {
	if (x.name != y.name) {
		return x.name < y.name;
	}
	else {
		return x.comp < y.comp;
	}
}

deque<point> dq;
ll dis[MAX];
ll color[MAX];
ll const INF = 1000000000000;

ll dijkstra(ll num_st) {
	REP(i, 1, num_st) {
		dis[i] = INF;
		color[i] = 0;
	}
	ll start = mp[{1, -1}];
	dis[start] = 0;
	dq.push_back({ start,0 });
	while (!dq.empty()){
		point cur_pt = dq.front();
		dq.pop_front();
		ll cur = cur_pt.name; ll d = cur_pt.dist;
		//cout << cur<< " ! " << st[cur].name<< endl;
		for (ll i = 0; i < G[cur].size(); i++) {
			ll next = G[cur][i];
			if (dis[next] > d) {
				dis[next] = d;
				dq.push_front({ next,d });
				if (st[next].name == n) {
					return d;
				}
			}
		}
		ll cur_st = st[cur].name;
		ll vv = cur - 1; ll uu = cur + 1;
		if (color[cur_st] == 0) {
			color[cur_st] = 1;
			while (st[vv].name == cur_st) {
				if (dis[vv] == INF) {
					dis[vv] = d + 1;
					dq.push_back({ vv,d + 1 });
				}
				vv--;
			}
			while (st[uu].name == cur_st) {
				if (dis[uu] == INF) {
					dis[uu] = d + 1;
					dq.push_back({ uu,d + 1 });
				}
				uu++;
			}
		}
	}
	return -1;
}

int main() {
	cin >> n >> m;
	st[0] = { -1,-2 };
	st[1] = { 1,-1 };
	mp[{1, -1}] = 1;
	REP(i, 1, m) {
		ll a, b, c;
		cin >> a >> b >> c;
		line[i] = { a,b,c };
		station s1 = { a,c }; station s2 = { b,c };
		if (mp[s1] == 0) {
			num_st++;
			mp[s1] = num_st;
			st[num_st] = s1;
		}if (mp[s2] == 0) {
			num_st++;
			mp[s2] = num_st;
			st[num_st] = s2;
		}
	}
	sort(st + 1, st + 1 + num_st, st_order);
	REP(i, 1, num_st) {
		mp[st[i]] = i;
	}
	st[num_st + 1] = { 100000000000,-1 };
	
	REP(i, 1, m) {
		ll a, b, c;
		a = line[i].from; b = line[i].to; c = line[i].comp;
		ll x = mp[{a, c}];
		ll y = mp[{b, c}];
		G[x].push_back(y);
		G[y].push_back(x);
		//cout << x << " " << y << endl;
	}
	cout << dijkstra(num_st) << endl;
	/*
	REP(i, 1, num_st) {
		cout << st[i].name << " " << st[i].comp << " " << dis[i] << endl;
	}
	*/
}

/*
struct edge {
	ll from; ll to; ll comp;
};
vector<edge> G[MAX];
ll dist[MAX];
struct station {
	ll name; ll com;
};
map<station, ll> mp;
station st[MAX];

deque<station> dq;
ll dis[MAX];
edge line[MAX];

ll dijkstra(ll start) {
	dq.push_back({ start,-1,0 });
	ll ans = -1;
	while (!dq.empty()) {
		station cur = dq.front();
		dq.pop_front();
		ll cur_st = cur.name;

	}
}

bool st_order(station x, station)
int main() {
	cin >> n >> m;
	REP(i, 1, m) {
		ll a, b, c;
		cin >> a >> b >> c;
		line[i] = { a,b,c };
		station
	}
	sort(line + 1, line + n + 1, st_order);
	ll ans = dijkstra(1);
	cout << ans << endl;
}
*/

Measured memory_bytes: 72576