#include <bits/stdc++.h>

#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define FOR(i,n,m) for(int i=(int)(n); i<=(int)(m); i++)
#define RFOR(i,n,m) for(int i=(int)(n); i>=(int)(m); i--)
#define ITR(x,c) for(__typeof(c.begin()) x=c.begin();x!=c.end();x++)
#define RITR(x,c) for(__typeof(c.rbegin()) x=c.rbegin();x!=c.rend();x++)
#define setp(n) fixed << setprecision(n)

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 (a>b) { a=b; return 1; } return 0; }

#define ll long long
#define vll vector<ll>
#define vi vector<int>
#define pll pair<ll,ll>
#define pi pair<int,int>

#define all(a) (a.begin()),(a.end())
#define rall(a) (a.rbegin()),(a.rend())
#define fi first
#define se second
#define pb push_back
#define ins insert

#define debug(a) cerr<<(a)<<endl
#define dbrep(a,n) rep(_i,n) cerr<<(a[_i])<<" "; cerr<<endl
#define dbrep2(a,n,m) rep(_i,n){rep(_j,m) cerr<<(a[_i][_j])<<" "; cerr<<endl;}

using namespace std;

template<class A, class B>
ostream &operator<<(ostream &os, const pair<A,B> &p){return os<<"("<<p.fi<<","<<p.se<<")";}
template<class A, class B>
istream &operator>>(istream &is, pair<A,B> &p){return is>>p.fi>>p.se;}

//-------------------------------------------------

int N,M;
int stat(int i, int j){return i*N+j;}

int main(void)
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    cin>>N>>M;
    vector<vector<pi>> G(N);
    rep(i,M){
        int a,b; char c; cin>>a>>b>>c; a--; b--;
        G[a].emplace_back(b,c-'a');
        G[b].emplace_back(a,c-'a');
    }
    vector<vi> F(N*N);
    rep(i,N)rep(j,N){
        int st = stat(i,j);
        vector<vi> v1(26),v2(26);
        for(auto u:G[i]){
            v1[u.se].pb(u.fi);
        }
        for(auto u:G[j]){
            v2[u.se].pb(u.fi);
        }
        rep(ch,26){
            auto &vv1 = v1[ch];
            auto &vv2 = v2[ch];
            int V1 = vv1.size();
            int V2 = vv2.size();
            rep(k,V1)rep(l,V2){
                int to = stat(vv1[k],vv2[l]);
                F[st].pb(to);
                F[to].pb(st);
            }
        }
    }
    vector<int> dist(N*N,-1); dist[stat(0,N-1)]=0;
    queue<int> que; que.push(stat(0,N-1));
    while(!que.empty()){
        int v = que.front(); que.pop();
        for(auto u:F[v]){
            if (dist[u]!=-1) continue;
            dist[u]=dist[v]+1;
            que.push(u);
        }
    }
    int ans = INT_MAX;
    rep(i,N){
        if (dist[stat(i,i)]!=-1)
            chmin(ans,dist[stat(i,i)]*2);
        for(auto e:G[i]){
            if (dist[stat(i,e.fi)]==-1) continue;
            chmin(ans,dist[stat(i,e.fi)]*2+1);
        }
    }
    if (ans==INT_MAX){
        cout<<"-1\n";
    }else{
        cout<<ans<<endl;
    }
    return 0;
}

//g++  7.4.0

#include <iostream>
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define MAXN 1005
vector<pair<ll,char>> adj[MAXN];
map<pair<ll,ll>,ll> vis;
map<pair<ll,ll>,ll> edge;
map<pair<ll,ll>,ll> dis;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    ll N,M; cin>>N>>M;
    for(ll i=0;i<M;++i)
    {
        ll u,v; cin>>u>>v;
        char ch; cin>>ch;
        adj[u].push_back({v,ch});
        adj[v].push_back({u,ch});
        edge[{u,v}] = 1;
        edge[{v,u}] = 1;
    }
    
    queue<pair<ll,ll>> q;
    dis[{1,N}] = 0;
    q.push({1,N});
    vis[{1,N}] = 1;
    ll ans = LLONG_MAX;
    
    while(!q.empty())
    {
        ll a = q.front().first;
        ll b = q.front().second;
        //cout<<a<<" "<<b<<endl;
        q.pop();
        
        if(a == b)
        {
            ans = min(ans,2LL * dis[{a,b}]);
            break;
        }
        
        if(edge[{a,b}])
        {
            ans = min(ans,2LL * dis[{a,b}] + 1);
            continue;
        }
        
        for(auto it1: adj[a])
        {
            for(auto it2: adj[b])
            {
                ll c = it1.first;
                ll d = it2.first;
                
                if(!vis[{c,d}] && (it1.second == it2.second))
                {
                    dis[{c,d}] = dis[{a,b}] + 1;
                    vis[{c,d}] = 1;
                    q.push({c,d});
                }
            }
        }
    }
    
    if(ans == LLONG_MAX)
        cout<<-1<<endl;
    else
        cout<<ans<<endl;
}