/*                                                       
  /^--^\                                                 
  \____/                                                 
 /      \ _____  _ __  __ ____  _     ____   ____  _____ 
|        || ()_)| |\ \/ /| ===|| |__ / (__` / () \|_   _|
 \__  __/ |_|   |_|/_/\_\|____||____|\____)/__/\__\ |_|  
|^|^\ \^|^|^|^|^|^|^|^|^|^|^|^|^|^|^|^|^|^|^|^|^|^|^|^|^|
| | |\ \| | | | | | | | | | | | | | | | | | | | | | | | |
#####/ /#################################################
| | |\/ | | | | | | | | | | | | | | | | | | | | | | | | |
|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|*/
//#pragma GCC optimize("O4,unroll-loops,no-stack-protector")
#include <bits/stdc++.h>
#define int ll //__int128
#define double long double
using namespace std;
using ll=long long;
using ull=unsigned long long;
using pii=pair<int,int>;

#define For(i,a,b)    for(int i=a;i<=b;i++)
#define Fors(i,a,b,s) for(int i=a;i<=b;i+=s)
#define Forr(i,a,b)   for(int i=a;i>=b;i--)
#define F first
#define S second
#define L(id) (id*2+1)
#define R(id) (id*2+2)
#define LO(x) (x&(-x))

#define eb emplace_back
#define all(x) x.begin(),x.end()
#define sz(x) ((int)x.size())
#define mkp make_pair

#define MOD (int)(1000000007)
#define INF (int)(1e12)
#define EPS (1e-7)

#ifdef NYAOWO
#define debug(...) do{\
	cerr << __LINE__ <<\
	" : ("#__VA_ARGS__ << ") = ";\
	_OUT(__VA_ARGS__);\
	cerr << flush;\
}while(0)
template<typename T> void _OUT(T x) { cerr << x << "\n"; }
template<typename T,typename...I>
void _OUT(T x,I ...tail) { cerr << x << ", "; _OUT(tail...); }
inline void USACO(const string &s) { cerr<<"USACO: "<<s<<"\n"; }
#else
#define debug(...)
inline void USACO(const string &s){
	freopen((s+".in").c_str(),"r",stdin);
	freopen((s+".out").c_str(),"w",stdout);
}
#endif
inline void NYA(){ ios::sync_with_stdio(false); cin.tie(0); }

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
//int gcd(int a,int b) { return b==0?a:gcd(b,a%b); }
inline int gcd(int a,int b) { return __gcd(a,b); }
inline int lcm(int a,int b) { return a/gcd(a,b)*b; }
int fpow(int b,int p,const int &mod){
	int ans=1;
	while(p){
		if(p&1) ans=ans*b%mod;
		p/=2; b=b*b%mod;
	}
	return ans;
}
int fpow(int b,int p) { return fpow(b,p,MOD); }
template<typename T> inline void chmin(T &_a,const T &_b) { if(_b<_a) _a=_b; }
template<typename T> inline void chmax(T &_a,const T &_b) { if(_b>_a) _a=_b; }

int dis[1010][1010];
vector<int> adj[1010][26];

int32_t main(){
	NYA();
	//nachoneko so cute >/////<
	int n,m; cin>>n>>m;
	memset(dis,-1,sizeof(dis));
	priority_queue<pair<int,pii>,vector<pair<int,pii>>,greater<pair<int,pii>>> pq;
	//pair( dist , pair( s,t ) ) where s<=t
	For(i,1,n) pq.emplace(0,mkp(i,i));
	while(m--){
		int a,b; cin>>a>>b;
		char ch; cin>>ch;
		adj[a][ch-'a'].eb(b);
		adj[b][ch-'a'].eb(a);
		if(a>b) swap(a,b);
		pq.emplace(1,mkp(a,b));
	}
	while(!pq.empty()){
		int d=pq.top().F;
		int s=pq.top().S.F;
		int t=pq.top().S.S;
		pq.pop();
		if(dis[s][t]!=-1) continue;
		dis[s][t]=d;
		For(ch,0,25){
			for(auto &a:adj[s][ch]) for(auto &b:adj[t][ch]){
				int x=min(a,b),y=max(a,b);
				if(dis[x][y]==-1) pq.emplace(d+2,mkp(x,y));
			}
		}
	}
	cout<<dis[1][n]<<"\n";
	return 0;
}
#pragma GCC optimize("Ofast") 
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define fi first
#define se second
#define sz(a) (int)(a.size())
#define all(a) a.begin(),a.end()
#define lb lower_bound
#define ub upper_bound
#define owo ios_base::sync_with_stdio(0);cin.tie(0);
#define MOD (ll)(1e9+7)
#define INF (ll)(1e18)
#define debug(...) fprintf(stderr, __VA_ARGS__),fflush(stderr)
#define time__(d) for(long blockTime = 0; (blockTime == 0 ? (blockTime=clock()) != 0 : false);\
debug("%s time : %.4fs\n", d, (double)(clock() - blockTime) / CLOCKS_PER_SEC))
typedef long long int ll;
typedef long double ld;
typedef pair<ll,ll> PII;
typedef pair<int,int> pii;
typedef vector<vector<int>> vii;
typedef vector<vector<ll>> VII;
typedef pair<int,pii> P;
ll gcd(ll a,ll b){if(!b)return a;else return gcd(b,a%b);}
VII dist(1001,vector<ll>(1001,INF));
vector<vector<pii>> adj(1001);
int main()
{
	int n,m;
	cin>>n>>m;
	for(int i=0;i<m;i++){
		int u,v;
		char c;
		cin>>u>>v>>c;
		c-='a';
		adj[v].pb({u,c});
		adj[u].pb({v,c});
	}
	queue<pii>q;
	dist[1][n] = 0;
	q.push({1,n});
	while(!q.empty()){
		pii v = q.front();
		q.pop();
		for(pii x:adj[v.fi]){
			for(pii y:adj[v.se]){
				if(x.se == y.se && dist[x.fi][y.fi] == INF){
					dist[x.fi][y.fi] = dist[v.fi][v.se]+2;
					q.push({x.fi,y.fi});
				}
			}
		}
		
	}
	ll ans = INF;
	for(int i=1;i<=n;i++){
		ans = min(ans,dist[i][i]);
		for(pii x:adj[i]){
			ans = min(ans,dist[i][x.fi] + 1);
		}
	}
	if(ans == INF)ans = -1;
	cout<<ans;
}
