#include<bits/stdc++.h>
#define FOR(i,a,b) for(int i=(a),i##end=(b);i<i##end;i++)
#define REP(i,a,b) for(int i=(a),i##end=(b);i<=i##end;i++)
#define RFOR(i,a,b) for(int i=(a),i##end=(b);i>i##end;i--)
#define RREP(i,a,b) for(int i=(a),i##end=(b);i>=i##end;i--)
typedef long long LL;

const int maxn=1000+5;

std::queue<std::pair<int,int> > Q;
int distance[maxn][maxn],n,m;
std::vector<int> G[maxn][26];
int main() {
	memset(distance,-1,sizeof(distance));
	while(!Q.empty()) Q.pop();
	scanf("%d%d",&n,&m);
	REP(u,1,n) FOR(i,0,26) G[u][i].clear();
	REP(u,1,n) Q.push(std::make_pair(u,u)),distance[u][u]=0;
	
	while(m--) {
		int x,y,c; scanf("%d%d",&x,&y);
		while(!isalpha(c=getchar()));
		c-=97;
		G[x][c].push_back(y);
		G[y][c].push_back(x);
		if(distance[x][y]<0) distance[x][y]=distance[y][x]=1,Q.push(std::make_pair(x,y));
	}
	
	while(!Q.empty()) {
		std::pair<int,int> p=Q.front(); Q.pop();
		int u=p.first,v=p.second;
		if((u==1&&v==n)||(u==n&&v==1)) { printf("%d\n",distance[1][n]); return 0; }
		FOR(c,0,26) FOR(i,0,G[u][c].size()) FOR(j,0,G[v][c].size()) {
			int us=G[u][c][i],vs=G[v][c][j];
			if(distance[us][vs]>=0) continue;
			distance[us][vs]=distance[vs][us]=distance[u][v]+2;
			Q.push(std::make_pair(us,vs));
		}
	}
	printf("-1\n");
	return 0;
}

#include<bits/stdc++.h>
//#include <atcoder/all>
#pragma GCC target("avx2")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")

#define rep(i,n)for(int i=0;(i)<(int)(n);i++)
#define REP(i,a,b)for(int i=(int)(a);(i)<=(int)(b);i++)
#define ALL(a)  (a).begin(),(a).end()
#define pb push_back
#define fi first
#define se second
#define sz(x) ((int)x.size())
 
using namespace std;
//using namespace atcoder;
using ld = long double;
using ll = long long;
using P = pair<ll, ll>;
 
template<typename T> bool chmin(T& a, const T& b) { if(a >= b){ a = b; return 1;} return 0; }
template<typename T> bool chmax(T& a, const T& b) { if(a <= b){ a = b; return 1;} return 0; }

const ll MOD = 1e9 + 7;
const ll INF = 1e16;


struct Edge{
    int to;
    char col;
};

int main(){
    int n, m;
    cin >> n >> m;
    vector<vector<Edge>> G(n);
    vector<int> a(m), b(m);
    rep(i, m){
        char c;
        cin >> a[i] >> b[i] >> c;
        a[i]--;b[i]--;
        G[a[i]].pb(Edge{b[i], c});
        G[b[i]].pb(Edge{a[i], c});
    }


    vector<vector<int>> nG(n * n);
    //グラフを再構築する
    auto push = [&](int ua, int ub, int va, int vb){
        nG[ua * n + ub].pb(va * n + vb);
    };
    rep(a, n){
        rep(b, n){
            for(auto ea : G[a]){
                for(auto eb : G[b]){
                    if(ea.col == eb.col)push(a, b, ea.to, eb.to);
                }
            }
        }
    }

    vector<ll> d(n * n, INF);
    priority_queue<P, vector<P>, greater<P>> pq;
    d[n - 1] = 0;
    pq.push(P(0, n - 1));

    while(sz(pq)){
        auto [cost, v] = pq.top();
        pq.pop();
        if(d[v] < cost)continue;
        for(auto nv : nG[v]){
            if(d[nv] > d[v] + 1){
                d[nv] = d[v] + 1;
                // cout << nv << " " << d[nv] << endl;
                pq.push(P(d[nv], nv));
            }
        }
    }
    ll res = INF;
    // rep(i, n)cout << d[i * n + i] << endl;
    rep(i, n)chmin(res, 2 * d[i * n + i]);
    rep(i, m){
        chmin(res, 2 * d[a[i] * n + b[i]] + 1);
        chmin(res, 2 * d[b[i] * n + a[i]] + 1);
    }
    if(res == INF)res = -1;
    cout << res << endl;
}