#include<deque>
#include<queue>
#include<vector>
#include<algorithm>
#include<iostream>
#include<set>
#include<cmath>
#include<tuple>
#include<string>
#include<chrono>
#include<functional>
#include<iterator>
#include<random>
#include<unordered_set>
#include<array>
#include<map>
#include<iomanip>
#include<assert.h>
#include<list>
#include<bitset>
#include<stack>
#include<memory>
#include<numeric>
#include <utility>


using namespace std;
typedef long long int llint;
typedef long double lldo;
#define mp make_pair
#define mt make_tuple
#define pub push_back
#define puf push_front
#define pob pop_back
#define pof pop_front
#define fir first
#define sec second
#define res resize
#define ins insert
#define era erase
#define REP(i, n) for(int i = 0;i < (n);i++)
/*cout<<fixed<<setprecision(20);cin.tie(0);ios::sync_with_stdio(false);*/
const llint mod=998244353;
const llint inf=2.19e15;
const long double pai=3.141592653589793238462643383279502884197;
const long double eps=1e-10;
template <class T,class U>bool chmin(T& a,U b){if(a>b){a=b;return true;}return false;}
template <class T,class U>bool chmax(T& a,U b){if(a<b){a=b;return true;}return false;}
llint gcd(llint a,llint b){if(a%b==0){return b;}else return gcd(b,a%b);}
llint lcm(llint a,llint b){if(a==0){return b;}return a/gcd(a,b)*b;}
template<class T> void SO(T& ve){sort(ve.begin(),ve.end());}
template<class T> void REV(T& ve){reverse(ve.begin(),ve.end());}
template<class T>llint LBI(T in,const vector<T>&ar){return lower_bound(ar.begin(),ar.end(),in)-ar.begin();}
template<class T>llint UBI(T in,const vector<T>&ar){return upper_bound(ar.begin(),ar.end(),in)-ar.begin();}

int main(void){
	cout<<fixed<<setprecision(20);cin.tie(0);ios::sync_with_stdio(false);
	int n,m,ans=mod,i,j;cin>>n>>m;
	vector<vector<pair<int,char>>>go(n);
	for(i=0;i<m;i++){
		int a,b;char c;cin>>a>>b>>c;
		a--;b--;
		go[a].pub(mp(b,c));
		go[b].pub(mp(a,c));
	}
	static int dp[1001][1001];
	for(i=0;i<n;i++){
		for(j=0;j<n;j++){dp[i][j]=mod;}
	}
	queue<tuple<int,int,int>>que;
	que.push(mt(0,n-1,0));
	dp[0][n-1]=0;
	while(que.size()){
		int a,b,d;tie(a,b,d)=que.front();que.pop();
		if(a==b){chmin(ans,d);}
		if(dp[a][b]>d){continue;}
		for(auto it:go[a]){
			for(auto jt:go[b]){
				if(it.sec==jt.sec){
					if(chmin(dp[it.fir][jt.fir],d+2)){que.push(mt(it.fir,jt.fir,d+2));}
				}
				if(it.fir==b&&jt.fir==a){chmin(ans,d+1);}
			}
		}
	}
	if(ans==mod){ans=-1;}
	cout<<ans<<endl;
	return 0;
}

#include <bits/stdc++.h>
using namespace std;
#define REP(i, n) for(int i = 0; i < n; i++)
#define REPR(i, n) for(int i = n - 1; i >= 0; i--)
#define FOR(i, m, n) for(int i = m; i <= n; i++)
#define FORR(i, m, n) for(int i = m; i >= n; i--)
#define SORT(v, n) sort(v, v+n);
#define VSORT(v) sort(v.begin(), v.end());
#define VSORTR(v) sort(v.rbegin(), v.rend());
#define ALL(v) (v).begin(),(v).end()
 
using ll = long long;
using vll = vector<ll>;
using vvll = vector<vector<ll>>;
using P = pair<ll, ll>;

template<typename T> using min_priority_queue = priority_queue<T, vector<T>, greater<T>>;
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }

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

//隣接リストのdijkstra
vll dijkstra(vvll &g, int s){
    vll d(g.size(), INF);
    d[s] = 0;
    priority_queue<P, vector<P>, greater<P>> que;
    que.push(P(0, s));
    while (!que.empty()){
        ll dist = que.top().first;
        int v = que.top().second;
        que.pop();
        if (d[v] < dist) continue;
        for (const auto &e: g[v]){
            if (d[e] <= d[v] + 1) continue;
            d[e] = d[v] + 1;
            que.push(P(d[e], e));
        }
    }
    return d;
}

int main(){
	cin.tie(0);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(10);

    ll n, m;
    cin >> n >> m;
    ll a, b;
    char c;
    vector<vector<P>> mem(26);
    vector<P> es(m);
    REP(i, m) {
        cin >> a >> b >> c;
        a--, b--;
        mem[c - 'a'].push_back(P{a, b});
        mem[c - 'a'].push_back(P{b, a});
        es[i] = P{a, b};
    }
    vvll g(n * n);
    REP(cc, 26) {
        for (auto e1 : mem[cc]) {
            for (auto e2 : mem[cc]) {
                ll x1 = e1.first, x2 = e1.second;
                ll y1 = e2.first, y2 = e2.second;
                g[n * x1 + y1].push_back(n * x2 + y2);
            }
        }
    }
    vll d = dijkstra(g, n - 1);
    ll res = INF;
    REP(i, n) {
        if (d[(n + 1) * i] == INF) continue;
        chmin(res, 2 * d[(n + 1) * i]);
    }
    REP(i, m) {
        a = es[i].first, b = es[i].second;
        if (abs(d[n * a + b] - d[n * b + a]) != 1) continue;
        chmin(res, 2 * max(d[n * a + b], d[n * b + a]) - 1);
    }
    if (res == INF) cout << -1 << endl;
    else cout << res << endl;
    return 0;
}