#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define REP(i, n) for(ll i = 0; i < (ll)(n); ++i)
#define FOR(i, a, b) for(ll i=(a); i < (ll)(b); ++i)
template<class T> inline bool chmax(T& a, T b) { if(a < b){ a=b; return 1; } return 0;}
template<class T> inline bool chmin(T& a, T b) { if(a > b){ a=b; return 1; } return 0;}

struct Edge{
	ll to;
	char c;
};
using pp = pair<ll,ll>;

int main(){
	// input
	ll n,m;
	cin >> n >> m;
	vector<vector<Edge>> graph(n);
	vector<vector<ll>> adj(n,vector<ll>(n,0));
	REP(i,m){
		int a,b;
		char c;
		cin >> a >> b >> c;
		a--; b--;
		adj[a][b] = 1;
		adj[b][a] = 1;
		{
			Edge e;
			e.to = b; e.c = c;
			graph[a].push_back(e);
		}
		if(a==b)continue;
		{
			Edge e;
			e.to = a; e.c = c;
			graph[b].push_back(e);
		}
	}
	
	
	vector<vector<vector<pp>>> dgraph(n);
	REP(i,n) dgraph[i].resize(n);
	
	REP(i,n){
		REP(j,n){
			for(auto ie:graph[i]){
				for(auto je:graph[j]){
					if(ie.c==je.c){
						dgraph[i][j].push_back(make_pair(ie.to, je.to));
					}
				}
			}
		}
	}
	
	const ll INF=1e18;
	queue<pp> q;
	vector<vector<ll>> cost(n,vector<ll>(n,INF));
	q.push({0, n-1});
	cost[0][n-1] = 0;
	while(!q.empty()){
		ll nowi = q.front().first;
		ll nowj = q.front().second;
		q.pop();
		ll co = cost[nowi][nowj];
		
		for(auto child : dgraph[nowi][nowj]){
			if(cost[child.first][child.second] != INF) continue;
			
			cost[child.first][child.second] = co + 1;
			q.push(child);
		}
	}
	
	ll ans = INF;
	REP(i,n){
		if(cost[i][i]==INF) continue;
		chmin(ans, cost[i][i]*2);
	}
	
	REP(i,n){
		REP(j,n){
			if(adj[i][j]==0) continue;
			
			if(cost[i][j]==INF)continue;
			chmin(ans, 2*cost[i][j] +1 );
		}
	}
	
	if(ans==INF){
		cout << "-1\n";
	}else{
		cout << ans << endl;
	}
	
	return 0;
}
#include <algorithm>
#include <cctype>
#include <cmath>
#include <cstring>
#include <iostream>
#include <sstream>
#include <numeric>
#include <map>
#include <set>
#include <unordered_set>
#include <unordered_map>
#include <queue>
#include <vector>

using namespace std;

typedef pair<int, int> II;

int solve(int N, int M, std::vector<int>& A, std::vector<int>& B, std::vector<char>& C) {
	vector<vector<pair<int, char>>> edges(N);
	for (int i = 0; i < M; i++) {
		edges[A[i]].emplace_back(make_pair(B[i], C[i]));
		edges[B[i]].emplace_back(make_pair(A[i], C[i]));
	}
	vector<vector<int>> visited(N, vector<int>(N));
	vector<II> q;
	q.emplace_back(II(0, N - 1));
	int ans = 1 << 30;
	for (int c = 2; !q.empty(); c += 2) {
		vector<II> nq;
		for (auto f : q) {
			int f_from = f.first;
			int r_from = f.second;
			for (auto fe : edges[f_from]) {
				int f_to = fe.first;
				int f_color = fe.second;
				if (f_to == r_from) {
					ans = min(ans, c - 1);
				}
				for (auto re : edges[r_from]) {
					int r_to = re.first;
					int r_color = re.second;
//					if (f_from == r_to) {
//						ans = min(ans, c - 1);
//					}
					if (f_color != r_color) continue;
					if (f_to == r_to) {
						ans = min(ans, c);
					}
					II key(f_to, r_to);
					if (!visited[f_to][r_to]) {
						visited[f_to][r_to] = 1;
						nq.emplace_back(II(f_to, r_to));
					}
				}
			}
		}
		if (ans < 1 << 30) return ans;
		q = nq;
	}
	return -1;
}

int main() {
	int N, M;
	std::cin >> N >> M;
	std::vector<int> A(M), B(M);
	std::vector<char> C(M);
	for (int i = 0; i < M; i++) {
		std::cin >> A[i] >> B[i] >> C[i];
		--A[i], --B[i];
	}
	cout << solve(N, M, A, B, C) << endl;
	return 0;
}
