#include<bits/stdc++.h>
#define M 1005
typedef long long ll;
using namespace std;
int stp[M][M][27];
int n,m;
vector<int> E[M][26];
struct node{int x,y,c;};
queue<node> Q;
int BFS(){
	int x,y,c;
	while(!Q.empty()){
		x=Q.front().x;
		y=Q.front().y;
		c=Q.front().c;
		if((c==26)&&((x==1&&y==n)||(x==n&&y==1)))return stp[x][y][26];
		Q.pop();
		if(c==26){
			for(int i=0;i<26;++i)
				for(int j=0,z;j<E[x][i].size();++j){
					if(~stp[z=E[x][i][j]][y][i])continue;
					stp[z][y][i]=stp[x][y][c]+1;
					Q.push((node){z,y,i});
				}
		}else{
			for(int j=0,z;j<E[y][c].size();++j){
				if(~stp[x][z=E[y][c][j]][26])continue;
				stp[x][z][26]=stp[x][y][c]+1;
				Q.push((node){x,z,26});
			}
		}
	}
	return -1;
}
int main(){
	cin>>n>>m; 
	memset(stp,-1,sizeof(stp));
	for(int i=1;i<=n;++i){
		stp[i][i][26]=0;
		Q.push((node){i,i,26});
	}
	int u,v;char c[5];
	for(int i=1;i<=m;++i){
		scanf("%d%d%s",&u,&v,c);
		if(u>v)swap(u,v);
		E[u][c[0]-'a'].push_back(v);
		E[v][c[0]-'a'].push_back(u);
		if(u==v)continue;
		stp[u][v][26]=1;
		stp[v][u][26]=1;
		Q.push((node){u,v,26});
		Q.push((node){v,u,26});
	}
	cout<<BFS();
	return 0;
}
//
// Created by yamunaku on 2021/03/27.
//

#include <bits/stdc++.h>
//#include <atcoder/all>

using namespace std;
//using namespace atcoder;

#define rep(i, n) for(int i = 0; i < (n); i++)
#define repl(i, l, r) for(int i = (l); i < (r); i++)
#define per(i, n) for(int i = ((n)-1); i >= 0; i--)
#define perl(i, l, r) for(int i = ((r)-1); i >= (l); i--)
#define all(x) (x).begin(),(x).end()
#define MOD9 998244353
#define MOD1 1000000007
#define IINF 1000000000
#define LINF 1000000000000000000
#define SP <<" "<<
#define CYES cout<<"Yes"<<endl
#define CNO cout<<"No"<<endl
#define CFS cin.tie(0);ios::sync_with_stdio(false)
#define CST(x) cout<<fixed<<setprecision(x)

using ll = long long;
using ld = long double;
using vi = vector<int>;
using mti = vector<vector<int>>;
using vl = vector<ll>;
using mtl = vector<vector<ll>>;
using pi = pair<int, int>;
using pl = pair<ll, ll>;
template<typename T>
using heap = priority_queue<T, vector<T>, function<bool(const T, const T)>>;

int main() {
    //CFS;
    int n, m;
    cin >> n >> m;
    vector<vector<vector<int>>> e(n, mti(26));
    priority_queue<pair<int, pair<int, int>>> q;
    rep(i, n) q.push({0, {i, i}});
    rep(i, m) {
        int a, b;
        char c;
        cin >> a >> b >> c;
        a--, b--;
        c -= 'a';
        e[a][c].push_back(b);
        e[b][c].push_back(a);
        q.push({-1, {a, b}});
        q.push({-1, {b, a}});
    }
    mti len(n, vi(n, IINF));
    while (!q.empty()) {
        auto now = q.top();
        q.pop();
        int x = now.second.first, y = now.second.second;
        if (len[x][y] != IINF) continue;
        len[x][y] = -now.first;
        rep(i, 26) {
            for (auto &nx : e[x][i]) {
                for (auto &ny : e[y][i]) {
                    if (len[nx][ny] != IINF) continue;
                    q.push({-len[x][y] - 2, {nx, ny}});
                }
            }
        }
    }
    if (len[0][n - 1] != IINF) cout << len[0][n - 1] << endl;
    else cout << -1 << endl;
    return 0;
}
