#include <bits/stdc++.h>
#define SZ(x) (int)(x).size()
#define ALL(x) (x).begin(),(x).end()
#define PB push_back
#define EB emplace_back
#define MP make_pair
#define FI first
#define SE second
using namespace std;
typedef double DB;
typedef long double LD;
typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int,int> PII;
typedef vector<int> VI;
typedef vector<PII> VPII;
// head
const int N=1e3+5;
VPII g[N];
int n,m;
bool st[N][N];
struct R {
    int u,v,d;
    R() {}
    R(int u,int v,int d):u(u),v(v),d(d) {}
    bool operator < (const R &T) const {
        return d>T.d;
    }
};
int bfs() {
    priority_queue<R> q;
    q.emplace(1,n,0);
    while(SZ(q)) {
        int u=q.top().u,v=q.top().v,d=q.top().d;
        q.pop();
        if(u==v) return d;
        if(st[u][v]) continue;
        st[u][v]=true;
        for(auto x:g[u]) if(x.FI==v) return d+1;
        for(auto x:g[u])
            for(auto y:g[v])
                if(!st[x.FI][y.FI]&&x.SE==y.SE) {
                    if(x.FI==y.FI) return d+2;
                    q.emplace(x.FI,y.FI,d+2);
                }
    }
    return -1;
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin>>n>>m;
    for(int i=1;i<=m;i++) {
        int u,v,w;
        char c;
        cin>>u>>v>>c;
        w=c-'a';
        g[u].EB(v,w);
        if(u!=v) g[v].EB(u,w);
    }
    cout<<bfs()<<'\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;
}