//Ô¸Éñ zhoukangyang Ö¸ÒýÎÒ¡£ 
#include <stdio.h>
#include <string.h>
#include <queue>
#define int long long
inline int read()
{
    int num=0,f=1;char c=getchar();
    while(c<48||c>57){if(c=='-')f=-1;c=getchar();}
    while(c>47&&c<58)num=(num<<3)+(num<<1)+(c^48),c=getchar();
    return num*f;
}
inline int min(int a,int b){return a<b?a:b;}
inline int max(int a,int b){return a>b?a:b;}
struct Edge{
	int v,w,nxt;
}e[2005];
int h[1005],cnt=1;
inline void addedge(int u,int v,int w)
{
	e[cnt]=(Edge){v,w,h[u]};
	h[u]=cnt++;
}
struct Node{
	int u,v,fu,fv,dis;
};
std::queue<Node> q;
inline int gc()
{
	char c=getchar();
	while(c<'a'||c>'z')c=getchar();
	return c;
}
int inq[1005][1005];
signed main()
{
    int n=read(),m=read(),curans=0;
    for(int i=0;i<m;i++)
    {
    	int x=read(),y=read(),z=gc();
    	addedge(x,y,z);
    	addedge(y,x,z);
	}
	Node x=(Node){1,n,1,n,0};
	q.push(x);inq[1][n]=1;
	while(!q.empty())
	{
		x=q.front();q.pop();
		int u=x.u,v=x.v,fu=x.fu,fv=x.fv,d=x.dis;
		if(curans&&curans<d)
		{
			printf("%lld\n",curans);
			return 0;
		}
		//printf("hi %lld %lld %lld!\n",u,v,d);
		if(u==v){printf("%lld\n",d);return 0;}
		for(int i=h[u];i;i=e[i].nxt)
		{
			if(e[i].v==v)
			{
				//printf("%lld\n",d+1);
				//return 0;
				curans=d+1;
				goto nxx;
			}
		}
		for(int i=h[u];i;i=e[i].nxt)
		{
			int V=e[i].v,w=e[i].w;
			for(int j=h[v];j;j=e[j].nxt)
			{
				int vv=e[j].v,ww=e[j].w;
				if(inq[V][vv]||inq[vv][V])continue;
				if(V==fu&&vv==fv)continue;
				if(w==ww)
				{
					inq[V][vv]=1;
					q.push((Node){V,vv,u,v,d+2});
				}
			}
		}
		nxx:;
	}
	if(curans)printf("%lld\n",curans);
	else puts("-1");
}
/* made by amunduzbaev */

//~ #include <ext/pb_ds/assoc_container.hpp>
//~ #include <ext/pb_ds/tree_policy.hpp>
#include "bits/stdc++.h"

using namespace std;
//~ using namespace __gnu_pbds;

#define ff first
#define ss second
#define pb push_back
#define mp make_pair
#define ub upper_bound
#define lb lower_bound
#define sz(x) (int)x.size()
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(),x.rend()
#define NeedForSpeed ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define vv vector
#define tut(x) array<int, x> 
#define int long long

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii; 
typedef vector<int> vii;
typedef vector<pii> vpii;
template<class T> bool umin(T& a, const T& b) {return a > b? a = b, true:false;}
template<class T> bool umax(T& a, const T& b) {return a < b? a = b, true:false;}
void usaco(string s) { freopen((s+".in").c_str(),"r",stdin);  
	freopen((s+".out").c_str(),"w",stdout); NeedForSpeed }
//~ template<class T> tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;

const int N = 1e3+5;
const int mod = 1e9+7;
const ll inf = 1e18;
const ld Pi = acos(-1);

#define MULTI 0
int n, m, k, s, t, q, ans, res, a[N];
int dis[N][N];
vv<pair<int, char>> edges[N];

void solve(int t_case){
	cin>>n>>m;
	for(int i=0;i<m;i++){
		int a, b; char c; cin>>a>>b>>c;
		edges[a].pb({b, c}), edges[b].pb({a, c});
	} for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) dis[i][j] = mod;
	dis[1][n] = 0;
	queue<pii> qq;
	qq.push({1, n});
	while(!qq.empty()){
		pii cur = qq.front(); qq.pop();
		for(auto a : edges[cur.ff]){
			for(auto b : edges[cur.ss]){
				if(a.ss != b.ss) continue;
				if(umin(dis[a.ff][b.ff], dis[cur.ff][cur.ss] + 1)) qq.push({a.ff, b.ff});
			}
		}
	}
	int res = mod;
	for(int i=1;i<=n;i++){
		umin(res, dis[i][i] * 2);
		for(auto x : edges[i]) umin(res, dis[i][x.ff]*2 + 1);
	} if(res != mod) cout<<res<<"\n";
	else cout<<-1<<"\n";
}

signed main(){
	NeedForSpeed
	if(MULTI){
		int t; cin>>t;
		for(int t_case = 1; t_case <= t; t_case++) solve(t_case);
	} else solve(1);
	return 0;
}
