#include<bits/stdc++.h>
#define rep(i , a , b) for(int i = a ; i <= b ; i ++)
#define fi first
#define se second
using namespace std;
const int N = 1e3 + 10;
int mp[N][N] , vis[N][N];
vector<int>G[N][30]; 
signed main()
{
	int n , m ;
	cin >> n >> m ;
	rep(i , 1 , m)
	{
		int u , v;
		char ch;
		cin >> u >> v >> ch;
		G[u][ch - 'a'].push_back(v);
		G[v][ch - 'a'].push_back(u);
		mp[u][v] = mp[v][u] = 1;
	}
	queue<pair<pair<int , int> , int>>que;
	int res = 1e9;
	que.push(make_pair(make_pair(1 , n) , 0));
	vis[1][n] = 1;
	while(!que.empty())
	{
		pair<pair<int , int> , int>q = que.front();
		que.pop();
		int x = q.fi.fi , y = q.fi.se , z = q.se;
		if(z > res) break ;
		if(x == y) res = min(res , z);
		if(mp[x][y]) res = min(res , z + 1);
		rep(k , 0 , 25)
		{
			for(auto i : G[x][k])
			{
				for(auto j : G[y][k])
				{
					if(vis[i][j]) continue ;
					vis[i][j] = 1;
					que.push(make_pair(make_pair(i , j) , z + 2));
				}
			}
		}
	}
	if(res == 1e9) res = -1;
	cout << res << '\n';
	return 0;
}
#include<bits/stdc++.h>
using namespace std;
const int N=1e6+1e5,M=1e3+10;
int n,m;
vector<int>e[N]; 
vector<int>f[M][26];
int a,b;
char c[5];
int d[N];
int cal(int x,int y){
	return x*1001+y;
}
queue<int>q;
int main(){
	scanf("%d%d",&n,&m);
	memset(d,-1,sizeof d);
	for(int i=1;i<=n;++i){
		d[cal(i,i)]=0;
		q.push(cal(i,i));
	}
	for(int i=1;i<=m;++i){
		scanf("%d%d%s",&a,&b,c);
		if(a!=b){
			d[cal(a,b)]=1;
			q.push(cal(a,b));
			d[cal(b,a)]=1;
			q.push(cal(b,a));
		}
		int v=c[0]-'a';
		f[a][v].push_back(b);
		f[b][v].push_back(a);
	}
	for(int i=1;i<=n;++i){
		for(int j=0;j<26;++j){
			for(auto &x:f[i][j]){
				for(int k=1;k<=n;++k){
					for(auto &y:f[k][j]){//i-x k-y
						e[cal(i,k)].push_back(cal(x,y));
						e[cal(i,k)].push_back(cal(y,x));
						e[cal(i,y)].push_back(cal(k,x));
						e[cal(i,y)].push_back(cal(x,k));
					}
				}
			}
		}
	}
	while(!q.empty()){
		int x=q.front();q.pop();
		//printf("(%d,%d):%d\n",x/1001,x%1001,d[x]);
		for(auto &y:e[x]){
			if(d[y]==-1){
				d[y]=d[x]+2;
				q.push(y);
			}
		}
	}
	printf("%d\n",d[cal(1,n)]);
	return 0;
}