#include<bits/stdc++.h>
using namespace std;

#define int long long 
#define ll long long 
#define ld long double
#define TIME clock() * 1.0 / CLOCKS_PER_SEC
#define sz(x) (int)(x.size())

template <typename A, typename B>
string to_string(pair<A, B> p);
 
template <typename A, typename B, typename C>
string to_string(tuple<A, B, C> p);
 
template <typename A, typename B, typename C, typename D>
string to_string(tuple<A, B, C, D> p);

string to_string(const string& s) {
    return '"' + s + '"';
}

string to_string(const char& s) {
    return to_string(string(1, s));
}
 
string to_string(const char* s) {
    return to_string((string) s);
}
 
string to_string(const bool& b) {
    return (b ? "1" : "0");
}
 
string to_string(const vector<bool>& v) {
	bool first = true;
	string res = "{";
	for (int i = 0; i < static_cast<int>(v.size()); i++) {
		if (!first) {
			res += ", ";
		}
		first = false;
		res += to_string(v[i]);
	}
	res += "}";
	return res;
}
 
template <size_t N>
string to_string(const bitset<N>& v) {
	string res = "";
	for (size_t i = 0; i < N; i++) {
		res += static_cast<char>('0' + v[i]);
	}
	return res;
}
 
template <typename A>
string to_string(const A& v) {
	bool first = true;
	string res = "{";
	for (const auto &x : v) {
		if (!first) {
			res += ", ";
		}
		first = false;
		res += to_string(x);
	}
	res += "}";
	return res;
}
 
template <typename A, typename B>
string to_string(pair<A, B> p) {
	return "(" + to_string(p.first) + ", " + to_string(p.second) + ")";
}
 
template <typename A, typename B, typename C>
string to_string(tuple<A, B, C> p) {
	return "(" + to_string(get<0>(p)) + ", " + to_string(get<1>(p)) + ", " + to_string(get<2>(p)) + ")";
}
 
template <typename A, typename B, typename C, typename D>
string to_string(tuple<A, B, C, D> p) {
    return "(" + to_string(get<0>(p)) + ", " + to_string(get<1>(p)) + ", " + to_string(get<2>(p)) + ", " + to_string(get<3>(p)) + ")";
}
 
void debug_out() { cerr << endl; }
 
template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
    cerr << " " << to_string(H);
    debug_out(T...);
}
 
#ifdef XOX // use -DXOX flag while compiling
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#else
#define debug(...) 42
#endif

const int inf = 1e15;

int32_t main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    // code here
    int n, m;
    cin >> n >> m;
    vector<array<int, 3>> edges;
    vector<int> dis(n * n, -1);
    for(int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        u--, v--;
        if(u > v) swap(u, v);
        dis[u * n + v] = 1;
        dis[v * n + u] = 1;
        char ch;
        cin >> ch;
        edges.push_back({u, v, (int)(ch - 'a')});
    }
    for(int i = 0; i < n; i++) {
        dis[i * n + i] = 0;
    }
    auto getp = [&](int u, int v) {
        if(u > v) swap(u, v);
        return u * n + v;
    };
    vector<vector<int>> adj(n * n);
    for(int i = 0; i < sz(edges); i++) {
        for(int j = i + 1; j < sz(edges); j++) {
            auto p1 = edges[i], p2 = edges[j];
            if(p1[2] != p2[2]) continue;
            int u = getp(p1[0], p2[0]);
            int v = getp(p1[1], p2[1]);
            adj[u].push_back(v);
            adj[v].push_back(u);

            u = getp(p1[0], p2[1]);
            v = getp(p1[1], p2[0]);
            adj[u].push_back(v);
            adj[v].push_back(u);
        }
    }
    debug(adj);
    debug(dis);
    vector<int> D(n * n, -1);
    queue<int> qu;
    qu.push(n - 1);
    D[n - 1] = 0;
    int ans = inf;
    while(!qu.empty()) {
        auto u = qu.front();
        qu.pop();
        if(dis[u] != -1) {
            ans = min(ans, D[u] + dis[u]);
            continue;
        }
        for(int v : adj[u]) {
            if(D[v] != -1) continue;
            D[v] = D[u] + 2;
            qu.push(v);
        }
    }
    cout << (ans == inf ? -1 : ans) << '\n';
    return 0;
}
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;

#define ff               first
#define ss               second
#define pb               push_back
#define all(x)           (x).begin(), (x).end()
#define mem0(x)          memset(x, 0, sizeof (x))
#define mem1(x)          memset(x, -1, sizeof (x))

typedef long long ll;
#define int ll
typedef vector <int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> ii;
typedef vector <ii> vii;
typedef vector<vii> vvii;

vvi g;

int32_t main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n, m; cin >> n >> m;
    g.assign(n*n, vi());
    vvii edges(26);
    for (int i = 0; i < m; ++i) {
        int u, v;
        char c;
        cin >> u >> v >> c;
        edges[c-'a'].pb({u-1, v-1});
    }
    for (int ch = 0; ch < 26; ++ch) {
        for (int i = 0; i < (int)edges[ch].size(); ++i) {
            for (int j = i+1; j < (int)edges[ch].size(); ++j) {
                int a,b,c,d;
                a = edges[ch][i].ff;
                b = edges[ch][i].ss;
                c = edges[ch][j].ff;
                d = edges[ch][j].ss;
                g[a*n+c].pb(b*n+d); g[b*n+d].pb(a*n+c);
                g[c*n+a].pb(d*n+b); g[d*n+b].pb(c*n+a);
                g[a*n+d].pb(b*n+c); g[b*n+c].pb(a*n+d);
                g[d*n+a].pb(c*n+b); g[c*n+b].pb(d*n+a);
            }
        }
    }
    vi dis(n*n, -1);
    queue<int> q;
    q.push(n-1);
    dis[n-1] = 0;
    while (q.size()){
        int u = q.front(); q.pop();
        for (int v: g[u]){
            if (dis[v] == -1){
                dis[v] = dis[u]+1;
                q.push(v);
            }
        }
    }
    int ans = 1e9;
    for (int i = 0; i < n; ++i) {
        if (dis[n*i+i] + 1) ans = min(ans, dis[n*i+i]*2);
    }
    for (int c = 0; c < 26; ++c) {
        for (ii p: edges[c]){
            if (dis[n*p.ff+p.ss] + 1) ans = min(ans, dis[n*p.ff+p.ss]*2+1);
            swap(p.ff, p.ss);
            if (dis[n*p.ff+p.ss] + 1) ans = min(ans, dis[n*p.ff+p.ss]*2+1);
        }
    }
    if (ans == (int)1e9) ans = -1;
    cout << ans << "\n";
}