#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); i++)
using namespace std;
using ll = long long;
using P = pair<int, int>;

const ll INF = 10e16;

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

    vector<vector<vector<P>>> G(n, vector<vector<P>>(n));
    rep(i, m) rep(j, m) {
        if (i == j) continue;
        if (c[i] != c[j]) continue;
        G[a[i]][a[j]].push_back({b[i], b[j]});
        G[b[i]][b[j]].push_back({a[i], a[j]});
        G[a[i]][b[j]].push_back({b[i], a[j]});
        G[b[i]][a[j]].push_back({a[i], b[j]});
    }

    vector<vector<ll>> dist(n, vector<ll>(n, INF));
    queue<P> que;

    dist[0][n - 1] = 0;
    que.push({0, n - 1});

    while (!que.empty()) {
        P p = que.front();
        que.pop();

        for (P np : G[p.first][p.second]) {
            if (dist[np.first][np.second] != INF) continue;
            dist[np.first][np.second] = dist[p.first][p.second] + 1;
            que.push(np);
        }
    }

    ll ans = INF;
    rep(i, n) ans = min(ans, dist[i][i] * 2);
    rep(i, m) {
        ans = min(ans, dist[a[i]][b[i]] * 2 + 1);
        ans = min(ans, dist[b[i]][a[i]] * 2 + 1);
    }

    if (ans == INF) ans = -1;
    cout << ans << endl;
}
#include <iostream>
#include <iomanip>
#include <string>
#include <vector>
#include <algorithm>
#include <utility>
#include <functional>
#include <set>
#include <map>
#include <queue>
#include <deque>
#include <bitset>
#include <math.h>
#include <random>
#include <chrono>
#include <assert.h>
using namespace std ;
using ll = long long ;
using ld = long double ;
template<class T> using V = vector<T> ;
template<class T> using VV = V<V<T>> ;
using pll = pair<ll,ll> ;
#define all(v) v.begin(),v.end()
ll mod = 1000000007 ;
long double pie = acos(-1) ;
ll INF = 1e18 ;

void yorn(bool a){if(a) cout << "Yes" << endl ; else cout << "No" << endl ;}
//void YorN(bool a){if(a) cout << "YES" << endl ; else cout << "NO" << endl ;}
ll gcd(long long a,long long b){if(b==0) return a ; return gcd(b,a%b) ;}
ll lcm(long long a,long long b){return a/gcd(a,b)*b ;}
ll extGCD(ll a,ll b,ll &x,ll &y){
    if(b==0){
        x = 1 ;
        y = 0 ;
        return a ;
    }
    ll d = extGCD(b,a%b,y,x) ;
    y -= a/b*x ;
    return d ;
}
void fix_cout(){cout << fixed << setprecision(20) ;}
template<class T> void chmax(T &a,T &b){if(a<b) a = b ;}
template<class T> void chmin(T &a,T &b){if(a>b) a = b ;}

int main(){
    int n,m ;
    cin >> n >> m ;
    VV<pair<int,char>> g(n) ;
    VV<V<ll>> edge(n,VV<ll>(26)) ;
    for(int i=0;i<m;i++){
        int a,b ;
        char c ;
        cin >> a >> b >> c ;
        a-- ; b-- ;
        g[a].emplace_back(b,c) ;
        g[b].emplace_back(a,c) ;
        edge[a][c-'a'].push_back(b) ;
        edge[b][c-'a'].push_back(a) ;
    }
    VV<ll> dp(n,V<ll>(n,INF)) ;
    dp[0][n-1] = 0 ;
    queue<pair<int,int>> q ;
    q.emplace(0,n-1) ;
    while(!q.empty()){
        int start = q.front().first ;
        int goal = q.front().second ;
        q.pop() ;
        for(auto p:g[start]){
            int nx = p.first ;
            char c = p.second; 
            for(auto &nx2:edge[goal][c-'a']){
                if(dp[nx][nx2]!=INF) continue ;
                dp[nx][nx2] = dp[start][goal]+2 ;
                q.emplace(nx,nx2) ;
            }
        }
    }
    ll ans = INF ;
    for(int i=0;i<n;i++) ans = min(ans,dp[i][i]) ;
    for(int i=0;i<n;i++) for(auto &p:g[i]) ans = min(ans,dp[i][p.first]+1) ;
    if(ans==INF) ans = -1 ;
    cout << ans << endl ;
}