#include <bits/stdc++.h>
using namespace std;

vector<pair<int,char>> adj[1000];
bool vis[1000][1000];
int best[1000][1000];

int main() {
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);

	int n, m;
	cin >> n >> m;

	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < n; ++j) {
			best[i][j] = 1e9;
		}
	}

	while (m--) {
		int u, v;
		char c;
		cin >> u >> v >> c, --u, --v;
		adj[u].emplace_back(v, c);
		adj[v].emplace_back(u, c);
	}

	best[0][n-1] = 0;
	queue<pair<int,int>> q;
	q.push({0, n-1});

	int ans = INT_MAX;

	while (!q.empty()) {
		int u, v;
		tie(u, v) = q.front();
		q.pop();
		if (vis[u][v]) continue;
		if (u == v) ans = min(ans, best[u][v]);
		vis[u][v] = true;
		for (auto [x1, c1] : adj[u]) {
			if (x1 == v) {
				ans = min(ans, best[u][v] + 1);
				continue;
			}
			for (auto [x2, c2] : adj[v]) {
				if (c1 == c2) {
					if (best[x1][x2] > best[u][v] + 2) {
						best[x1][x2] = best[u][v] + 2;
						q.push({x1, x2});
					}
				}
			}
		}
	}

	if (ans == INT_MAX) cout << "-1";
	else cout << ans;

	return 0;
}

#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define pre(i,a,b) for(int i=a;i>=b;i--)
#define N 1005
using namespace std;
int n,m,v[N][N],vis[N][N],ans=0x7fffffff;
vector<int>c[N][26];
struct node{
	int x,y,val;
	node(int X=0,int Y=0,int V=0){x=X;y=Y;val=V;}
	bool operator<(const node o)const{return val>o.val;}
};
priority_queue<node>q;
int main(){
	scanf("%d%d",&n,&m);
	rep(i,1,n)v[i][i]=1;
	rep(i,1,m){
		int x,y;char op[2];
		scanf("%d%d%s",&x,&y,op);
		v[x][y]=v[y][x]=1;
		c[x][(*op)-'a'].push_back(y);
		c[y][(*op)-'a'].push_back(x);
	}
	q.push(node(1,n,0));
	while(!q.empty()){
		node now=q.top();q.pop();
		vis[now.x][now.y]=1;
		if(now.x==now.y){printf("%d\n",min(ans,now.val*2));return 0;}
		if(v[now.x][now.y]){ans=min(ans,now.val*2+(now.x!=now.y));continue;}
		rep(col,0,25){
			for(int i=0;i<(int)c[now.x][col].size();i++)
				for(int j=0;j<(int)c[now.y][col].size();j++){
					int x=c[now.x][col][i],y=c[now.y][col][j];
					if(!vis[x][y])vis[x][y]=1,q.push(node(x,y,now.val+1));
				}
		}
	}
	if(ans==0x7fffffff)puts("-1");else printf("%d\n",ans);
	return 0;
}
