// Template
#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>
#include <iomanip>
#include <tuple>
#include <utility>
#include <queue>
#include <set>
#include <map>
#define rep_override(x, y, z, name, ...) name
#define rep2(i, n) for (int i = 0; i < (int)(n); ++i)
#define rep3(i, l, r) for (int i = (int)(l); i < (int)(r); ++i)
#define rep(...) rep_override(__VA_ARGS__, rep3, rep2)(__VA_ARGS__)
#define all(x) (x).begin(), (x).end()
using namespace std;
using ll = long long;
constexpr int inf = 1001001001;
constexpr ll infll = 3003003003003003003LL;
template <typename T>
inline bool chmin(T &x, const T &y) {
    if (x > y) {
        x = y;
        return true;
    }
    return false;
}
template <typename T> 
inline bool chmax(T &x, const T &y) {
    if (x < y) {
        x = y;
        return true;
    }
    return false;
}
template <typename T>
istream &operator>>(istream &is, vector<T> &vec) {
    for (T &element : vec) is >> element;
    return is;
}
template <typename T>
ostream &operator<<(ostream &os, const vector<T> &vec) {
    for (int i = 0, vec_len = (int)vec.size(); i < vec_len; ++i) {
        os << vec[i] << (i + 1 == vec_len ? "" : " ");
    }
    return os;
}
struct IOSET {
    IOSET() {
        cin.tie(nullptr);
        ios::sync_with_stdio(false);
        cout << fixed << setprecision(10);
    }
} ioset;

// Main
int main() {
    int n, m;
    cin >> n >> m;
    vector<int> a(m), b(m), c(m);
    rep(i, m) {
        int u, v;
        char ch;
        cin >> u >> v >> ch;
        a[i] = u - 1;
        b[i] = v - 1;
        c[i] = ch - 'a';
    }
    
    vector<vector<int>> g(n * n);
    rep(i, m) rep(j, m) {
        if (c[i] == c[j]) {
            g[a[i] * n + a[j]].push_back(b[i] * n + b[j]);
            g[a[i] * n + b[j]].push_back(b[i] * n + a[j]);
            g[b[i] * n + a[j]].push_back(a[i] * n + b[j]);
            g[b[i] * n + b[j]].push_back(a[i] * n + a[j]);
        }
    }
    
    vector<int> dist(n * n, inf);
    queue<int> que;
    rep(i, n) {
        dist[i * n + i] = 0;
        que.push(i * n + i);
    }
    rep(i, m) {
        if (chmin(dist[a[i] * n + b[i]], 1)) que.push(a[i] * n + b[i]);
        if (chmin(dist[b[i] * n + a[i]], 1)) que.push(b[i] * n + a[i]);
    }
    while (!que.empty()) {
        int v = que.front();
        que.pop();
        for (int u : g[v]) {
            if (chmin(dist[u], dist[v] + 2)) que.push(u);
        }
    }
    
    int ans = dist[n - 1];
    if (ans == inf) ans = -1;
    cout << ans << "\n";
}
#include<bits/stdc++.h>
using namespace std;

struct edge {
	int to;
	int c;
	edge(int to, int c) : to(to), c(c) {}
};

const int INF = 1001001001;

int main()
{
	int n, m;
	cin >> n >> m;
	vector<vector<edge>> g(n);
	for(int i = 0; i < m; i++) {
		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<vector<int>> dp(n, vector<int>(n, INF));
	queue<pair<int, int>> q;
	auto push = [&](int a, int b, int x) {
		if(dp[a][b] != INF) return;
		dp[a][b] = x;
		q.emplace(a, b);
	};
	push(0, n - 1, 0);
	while(!q.empty()) {
		auto [a, b] = q.front();
		q.pop();
		for(auto&& ea : g[a]) {
			for(auto&& eb : g[b]) {
				if(ea.c != eb.c) continue;
				push(ea.to, eb.to, dp[a][b] + 1);
			}
		}
	}
	int ans = INF;
	for(int i = 0; i < n; i++) {
		ans = min(ans, dp[i][i] * 2);
		for(auto&& e : g[i]) ans = min(ans, dp[i][e.to] * 2 + 1);
	}
	if(ans == INF) ans = -1;
	cout << ans << endl;
	return 0;
}