#include<bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp> 
//#include <ext/pb_ds/tree_policy.hpp>
#define ll long long int
#define ld long double
#define pb push_back
#define fi first
#define se second
#define all(x) x.begin(),x.end()
#define mem(x,y) memset(x,y,sizeof(x))
#define pii pair<int,int>
#define pll pair<ll,ll>
#define INF 1e9
#define INFL 1e18
//#define mod 1000000007
#define mod 998244353
#define fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
using namespace std;
//using namespace __gnu_pbds; 
//typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> os;
//typedef tree<pii,null_type,less<pii>,rb_tree_tag,tree_order_statistics_node_update> os_pair;

ll power(ll x,ll n){ll res =1;while(n>0){if(n%2==1){res=res*x;}x=x*x;n=n/2;}return res;}
ll powm(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}

//cout<< fixed << setprecision(10)
//__builtin_popcountll()
//https://qr.ae/pG7uXl

vector<pii>g[1005];
int main(){
	fast;
	int n,m,i,j;
	cin>>n>>m;
	vector<pii>v;
	for(i=0;i<m;i++)
	{
		int x,y;
		char c;
		cin>>x>>y>>c;
		v.pb({x,y});
		g[x].pb({y,c-'a'});
		g[y].pb({x,c-'a'});
	}
	queue<pii>q;
	q.push({1,n});
	int dp[n+1][n+1];
	int vis[n+1][n+1];
	mem(vis,0);
	for(i=1;i<=n;i++)
	{
		for(j=1;j<=n;j++)
			dp[i][j]=INF;

	}
	dp[1][n]=0;
	vis[1][n]=1;
	int ans=INF;
	while(q.size()!=0)
	{
		auto z=q.front();
		q.pop();
		for(auto x:g[z.fi])
		{
			for(auto y:g[z.se])
			{
				if(x.se==y.se)
				{
					if(dp[x.fi][y.fi]>dp[z.fi][z.se]+1)
					{
						dp[x.fi][y.fi]=dp[z.fi][z.se]+1;
						q.push({x.fi,y.fi});
						vis[x.fi][y.fi]=1;
					}
				}
			}
		}
	}
	for(i=1;i<=n;i++)
	{
		ans=min(ans,dp[i][i]*2);
	}
	for(i=0;i<m;i++)
	{
		ans=min(ans,dp[v[i].se][v[i].fi]*2+1);
		ans=min(ans,dp[v[i].fi][v[i].se]*2+1);
	}
	if(ans==INF)
		cout<<-1<<"\n";
	else
		cout<<ans;


	
}
#pragma GCC optimize(2)
#pragma GCC optimize(3,"Ofast","inline")
#include <bits/stdc++.h>
#define inf 0x7fffffff
#define ll long long
//#define int long long
//#define double long double
#define eps 1e-8
//#define mod 1e9+7
#define ls(p) p<<1
#define rs(p) p<<1|1
#define pi acos(-1.0)
using namespace std;
const int mod=1e9+7;
const int M=5e6;
const int N=4*1e3+5;//?????????? 4e8
int v[N][N],d[N][N];
int n,m;
struct node
{
	int next,ver;
}e[N];
int tot,head[N];
queue < pair < int , int > > q;
void add(int x,int y)
{
	e[++tot].ver=y;
	e[tot].next=head[x];
	head[x]=tot;
}
void addedge(int x,int y)
{
	add(x,y);add(y,x);
}
int bfs()
{
	while(q.size())
	{
		int x1=q.front().first;
		int x2=q.front().second;
		q.pop();
		for(int i1=head[x1];i1;i1=e[i1].next)  for(int i2=head[x2];i2;i2=e[i2].next)
		{
			int y1=e[i1].ver;
			int y2=e[i2].ver;
			if(d[x1][y1]==d[x2][y2]&&v[y1][y2]==-1)//两边扩展 
			{
				v[y1][y2]=v[x1][x2]+2;
				q.push(make_pair(y1,y2));
			}
		}
	} 
	return v[1][n];
}
void solve()
{
	cin>>n>>m;
	memset(v,-1,sizeof(v));
	for(int i=1;i<=n;i++)  q.push(make_pair(i,i)),v[i][i]=0;//偶对称，由于是求最小对称，所以要先进队 
	for(int i=1;i<=m;i++)
	{
		int x,y;
		char z;
		cin>>x>>y>>z;
		addedge(x,y);
		d[x][y]=d[y][x]=z;
		if(v[x][y]==-1)
		{
			q.push(make_pair(x,y));q.push(make_pair(y,x));//奇对称 
			v[x][y]=v[y][x]=1;
		}
	}
	cout<<bfs();
}
signed main()
{
    int T=1;
//    cin>>T;
    for(int index=1;index<=T;index++)
    {
        solve();
//        puts("");
    }
    return 0;
}