#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;i++)
#define cinf(n,x) for(int i=0;i<(n);i++)cin>>x[i];
#define ft first
#define sc second
#define pb push_back
#define lb lower_bound
#define ub upper_bound
#define all(v) (v).begin(),(v).end()
#define LB(a,x) lb(all(a),x)-a.begin()
#define UB(a,x) ub(all(a),x)-a.begin()
#define mod 1000000007
//#define mod 998244353
#define FS fixed<<setprecision(15)
using namespace std;
typedef long long ll;
const double pi=3.141592653589793;
template<class T> using V=vector<T>;
using P=pair<ll,ll>;
typedef unsigned long long ull;
typedef long double ldouble;
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline void out(T a){ cout << a << '\n'; }
void YN(bool ok){if(ok) cout << "Yes" << endl; else cout << "No" << endl;}
//void YN(bool ok){if(ok) cout << "YES" << endl; else cout << "NO" << endl;}


const ll INF=1e18;
const int mx=200005;
//abc197
struct edge{
    int to;
    char C;
};

int main(){
    //オーバーフローは大丈夫ですか？？
    cin.tie(0);ios::sync_with_stdio(false);
    int n,m;
    cin>>n>>m;
    V<V<edge>> G(n);
    rep(i,m){
        int a,b;
        char c;
        cin>>a>>b>>c;
        a--;b--;
        G[a].pb({b,c});
        G[b].pb({a,c});
    }
    V<V<ll>> dp(n,V<ll>(n,INF));
    /*function<ll(int,int,int,int)> rec=[&](int u,int v,int p1,int p2){
        //cout<<u<<' '<<v<<endl;
        if(u==v){
            //cout<<"="<<endl;
            dp[u][v]=dp[v][u]=0;
            return 0LL;
        }
        int f=0;
        for(edge e:G[v]){
            if(e.to==u) f=1;
        }
        if(f){
            dp[u][v]=dp[v][u]=1;
            return 1LL;
        }
        ll &res=dp[u][v];
        if(res<INF) return res;
        for(edge e1:G[u]){
            for(edge e2:G[v]){
                if(e1.C==e2.C){
                    if(!(e1.to==p1&&e2.to==p2))res=min(res,2LL+rec(e1.to,e2.to,u,v));
                    //res=min(res,2LL+dp[e2.to][e1.to]);
                }
            }
        }
        //dp[v][u]=res;
        return res;
    };
    ll ans=rec(0,n-1,-1,-1);
    if(ans==INF) ans=-1;
    out(ans);*/
    rep(i,n){
        for(edge e1:G[i]){
            for(edge e2:G[i]){
                if(e1.C==e2.C){
                    dp[e1.to][e2.to]=2;
                    dp[e2.to][e1.to]=2;
                }
            }
        }
    }
    rep(i,n) dp[i][i]=0;
    rep(i,n){
        for(edge e:G[i]) dp[i][e.to]=dp[e.to][i]=1;
    }
    priority_queue<pair<ll,P>,V<pair<ll,P>>,greater<pair<ll,P>>> que;
    rep(i,n){
        rep(j,n){
            if(dp[i][j]<INF) que.push({dp[i][j],{i,j}});
        }
    }
    while(que.size()){
        pair<ll,P> p=que.top();
        que.pop();
        int u=p.sc.ft;
        int v=p.sc.sc;
        for(edge e1:G[u]){
            for(edge e2:G[v]){
                if(e1.C==e2.C){
                    if(dp[e1.to][e2.to]>dp[u][v]+2){
                        dp[e1.to][e2.to]=dp[u][v]+2;
                        que.push({dp[e1.to][e2.to],{e1.to,e2.to}});
                    }
                }
            }
        }
    }
    ll ans=dp[0][n-1];
    if(ans==INF) ans=-1;
    out(ans);
}
//ペナルティ出しても焦らない　ACできると信じろ！！！
//どうしてもわからないときはサンプルで実験　何か見えてくるかも
//頭で考えてダメなら紙におこせ！！
#include <bits/stdc++.h>

using namespace std;

void solve() {
    int n, m;
    cin >> n >> m;
    vector<vector<vector<int>>> adj_list(n, vector<vector<int>>(26));
    vector<pair<int, int>> edges(m);
    for (int i = 0; i < m; ++i) {
        int a, b;
        char cc;
        cin >> a >> b >> cc;
        int c = (int) (cc - 'a');
        --a;
        --b;
        adj_list[a][c].push_back(b);
        adj_list[b][c].push_back(a);
        edges[i] = {a, b};
    }
    vector<int> dist(n*n, -1);
    queue<pair<int, int>> q;
    q.push({0, n - 1});
    dist[0 * n + (n - 1)] = 0;
    while (!q.empty()) {
        auto [u, v] = q.front();
        q.pop();
        int d = dist[u * n + v];
        for (int c = 0; c < 26; ++c) {
            for (int u1 : adj_list[u][c]) {
                for (int v1 : adj_list[v][c]) {
                    int w = u1 * n + v1;
                    if (dist[w] == -1) {
                        dist[w] = d + 1;
                        q.push({u1, v1});
                    }
                }
            }
        }
    }
    int best = numeric_limits<int>::max();
    for (int i = 0; i < n; ++i) {
        if (dist[i * n + i] != -1) {
            best = min(best, dist[i * n + i] * 2);
        }
    }
    for (auto [u, v] : edges) {
        if (dist[u * n + v] != -1) {
            best = min(best, dist[u * n + v] * 2 + 1);
        }
        if (dist[v * n + u] != - 1) {
            best = min(best, dist[v * n + u] * 2 + 1);
        }
    }
    if (best != numeric_limits<int>::max()) {
        cout << best << "\n";
    } else {
        cout << "-1\n";
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    solve();
    return 0;
}