103

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <queue>

using namespace std;

int n, m;
vector<vector<pair<int, int>>> g;
const int N = 201;
const int INF = 1000000000;
int d[N][N][4];
int p[N];

void bfs(){
	for(int k = 0; k < N; k++){
		for(int i = 0; i < N; i++)
			for(int j = 1; j < 4; j++){
				d[k][i][j] = INF;
			}
		p[k] = -1;
	}
	p[0] = 0;
	d[0][0][1] = d[0][0][2] = d[0][0][3] = 0;
	vector<bool> used(n);
	used[0] = true;
	queue<int> q;
	q.push(0);
	while(!q.empty()){
		int u = q.front();
		if(u == n-1){
			cout << min(min(d[p[u]][u][1], d[p[u]][u][2]), d[p[u]][u][3]) << endl; //?
			exit(0);
		}
		q.pop();
		for(int i = 0; i < g[u].size(); i++){
			if(!used[i] && g[u][i]){
				q.push(i);
				used[i] = true;
				p[i] = u;
				d[p[u]][i][g[u][i].second] = d[u] + 1;
			}
		}
	}
	cout << -1 << endl;
}

int main()
{
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
#endif
	scanf("%d%d", &n, &m);
	g = vector<vector<pair<int, int>>> (n);
	for(int i = 0; i < m; i++)
	{
		int x, y, c;
		scanf("%d%d%d", &x, &y, &c);
		x--; y--;
		g[x].push_back(make_pair(y, c));
	}

	bfs();

	return 0;
}//bug