#include <algorithm>
#include <cctype>
#include <cmath>
#include <cstring>
#include <iostream>
#include <sstream>
#include <numeric>
#include <map>
#include <set>
#include <unordered_set>
#include <unordered_map>
#include <queue>
#include <vector>

using namespace std;

typedef pair<int, int> II;
inline II make_key(int a, int b) {
	return make_pair(min(a, b), max(a, b));
}

int solve(int N, int M, std::vector<int> &A, std::vector<int> &B, std::vector<char> &C) {
	vector<vector<int>> v(26);
	for (int i = 0; i < M; i++) {
		v[C[i] - 'a'].emplace_back(i);
	}
	map<II, set<II>> m;
	set<II> adj;
	for (int ch = 0; ch < 26; ++ch) {
		for (int i = 0; i < v[ch].size(); ++i) {
			int a = A[v[ch][i]], c = B[v[ch][i]];
			adj.emplace(make_key(a, c));
			for (int j = i + 1; j < v[ch].size(); ++j) {
				int b = A[v[ch][j]], d = B[v[ch][j]];
				m[make_key(a, b)].insert(make_key(c, d));
				m[make_key(a, d)].insert(make_key(b, c));
				m[make_key(b, c)].insert(make_key(a, d));
				m[make_key(c, d)].insert(make_key(a, b));
			}
		}
	}
	set<II> q;
	q.emplace(II(0, N - 1));
	for (int i = 0; i < M && !q.empty(); ++i) {
			set<II> nq;
		for (auto x : q) {
			if (adj.find(x) != adj.end()) {
				return i * 2 + 1;
			}
			for (auto y : m[x]) {
				if (y.first == y.second) {
					return (i + 1) * 2;
				}
				nq.insert(y);
			}
		}
		q = nq;
	}
	return -1;
}

int main() {
    int N, M;
	std::cin >> N >> M;
	std::vector<int> A(M), B(M);
	std::vector<char> C(M);
	for (int i = 0; i < M; i++) {
		std::cin >> A[i] >> B[i] >> C[i];
		--A[i], --B[i];
	}
	cout << solve(N, M, A, B, C) << endl;
	return 0;
}

#include <bits/stdc++.h>
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()
using namespace std;

typedef long long ll;
typedef unsigned long long llu;
typedef pair<int, int> pii;
typedef pair<double, double> pdd;
typedef pair<int, pii> piii;
typedef pair<ll, ll> pll;
typedef pair<ll, int> pli;
typedef pair<int, ll> pil;
typedef pair<string, int> psi;
typedef pair<char, int> pci;
typedef pair<int, char> pic;
const int MOD = 1e9 + 7;
const long double PI = 3.141592653589793238462643383279502884197;

ll fac[1] = {1}, inv[1] = {1};
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
ll mp(ll a,ll b){ll ret=1;while(b){if(b&1)ret=ret*a%MOD;a=a*a%MOD;b>>=1;}return ret;}
ll cmb(ll r, ll c) {return (c>r||c<0) ? 0:fac[r] * inv[c] % MOD * inv[r - c] % MOD;}

vector<pci> v[1000];
int dist[1000][1000][27];

/*
int go(int o, int oo, int al) {
    if (o == oo) return 0;
    if (dp[o][oo][al] != -1) return dp[o][oo][al];

    int miv = 1e9;


    return dp[o][oo][al];
}*/

struct node {
    int o, oo, al;
};
queue<node> q;

int main() {
    memset(dist, -1, sizeof(dist));
    int n, m;
    scanf("%d %d", &n, &m);

    for (int i = 0; i < m; i++) {
        int a,b;
        char c;
        scanf("%d %d %c", &a, &b, &c);
        a--; b--;
        c -= 'a';
        v[a].push_back({c, b});
        v[b].push_back({c, a});
    }

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

    while (!q.empty()) {
        node tv = q.front();
        q.pop();

        int o = tv.o, oo = tv.oo, al = tv.al, co = dist[o][oo][al];
        if (o == oo) return !printf("%d", co);

        if (al == 26) {
            for (pci i : v[o]) {
                if (dist[i.second][oo][i.first] == -1) {
                    dist[i.second][oo][i.first] = co + 1;
                    q.push({i.second, oo, i.first});
                }
            }
        }
        else {
            for (pci i : v[oo]) {
                if (i.first == al && dist[o][i.second][26] == -1) {
                    dist[o][i.second][26] = co + 1;
                    q.push({o, i.second, 26});
                }
            }
        }
    }
    printf("-1");
}

// author: rdd6584
