#include <bits/stdc++.h>
using namespace std;
typedef long long ll; //int:2*10**9
typedef long double ld;
typedef pair<ll,ll> P;
#define REP(i,n) for(ll i = 0; i<(ll)(n); i++)
#define FOR(i,a,b) for(ll i=(a);i<=(b);i++)
#define FORD(i,a,b) for(ll i=(a);i>=(b);i--)
#define pb push_back
#define MOD 1000000007 //998244353
#define PI 3.141592653
#define INF 100000000000000 //14
//cin.tie(0);cout.tie(0);ios::sync_with_stdio(false);
#define N 1010

vector<vector<ll>> ansl(N,vector<ll>(N,INF));
vector<vector<vector<ll>>> conn(N,vector<vector<ll>>(26));

int main(){
    ll n, m; cin >> n >> m;
    REP(i,m) {
        ll a, b; char c; cin >> a >> b >> c;
        a--; b--; c-='a';
        conn[a][c].pb(b); conn[b][c].pb(a);
    }
    ansl[0][n-1]=0;
    queue<P> q;
    q.push({0,n-1});
    while (!q.empty()) {
        ll x = q.front().first; ll y = q.front().second; q.pop();
        REP(i,26) {
            for (ll nex : conn[x][i]) for (ll ney : conn[y][i]) if (ansl[nex][ney]==INF) {
                ansl[nex][ney]=ansl[x][y]+1;
                q.push({nex,ney});
            }
        }
    }
    ll ans = INF;
    REP(i,n) ans = min(ans,2*ansl[i][i]);
    REP(i,n) {
        REP(j,26) for (ll k : conn[i][j]) {
            ans = min(ans,2*ansl[i][k]+1);
        }
    }
    if (ans==INF) cout << -1 << endl;
    else cout << ans << endl;
    return 0;
}
#include <iostream>
#include <queue>
#include <string>
#include <vector>
using namespace std;
int n, m;
vector<pair<int, char>> edges[1000];
int main()
{
    cin >> n >> m;
    for (int i = 0; i < n; ++i)
        edges[i].clear();
    for (int i = 0; i < m; ++i) {
        int from, to;
        char c;
        cin >> from >> to >> c;
        --from;
        --to;
        edges[from].push_back({ to, c });
        edges[to].push_back({ from, c });
    };
    queue<pair<int, int>> q, qq;
    q.push(make_pair(0, n - 1));
    int d = 0;
    int res = -1;
    bool visited[1000][1000] = { 0 };
    while (!q.empty()) {
        while (!q.empty()) {
            auto front = q.front();
            q.pop();
            int x = front.first;
            int y = front.second;
            for (auto edgeA : edges[x]) {
                for (auto edgeB : edges[y]) {
                    if (edgeA.second != edgeB.second)
                        continue;
                    if (visited[edgeA.first][edgeB.first])
                        continue;
                    visited[edgeA.first][edgeB.first] = true;
                    if (edgeA.first == edgeB.first) {
                        res = (res == -1 || res > 2 * (d + 1)) ? 2 * (d + 1) : res;
                    } else if (edgeA.first == y && edgeB.first == x) {
                        res = (res == -1 || res > 2 * d + 1) ? 2 * d + 1 : res;
                    } else {
                        qq.push(make_pair(edgeA.first, edgeB.first));
                    }
                }
            }
        }
        swap(q, qq);
        ++d;
    }
    cout << res << endl;
    return 0;
}
