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

using P = pair<int, int>;

//Graph[i][j][k] ==> i 番目のアルファベットが置かれている
//辺のうち、j から出ている k 番目の辺がつなぐ j 以外の頂点

vector<int> Graph[26][1000];

int main()
{
    int N, M;
    cin >> N >> M;
    //作れるどんな回文の大きさよりも大きい数（今回はどんなに長くても N * N * 2 とかだねたぶん）
    int inf = 1 << 30;
    //真ん中に一文字入れたら回文ができるところで使う
    vector<P> edges;
    //辺の情報を入力
    for (int i = 0; i < M; i++)
    {
        int u, v;
        char c;
        cin >> u >> v >> c;
        u--;
        v--;
        int type = c - 'a';
        Graph[type][v].push_back(u);
        Graph[type][u].push_back(v);
        edges.push_back(P(u, v));
        edges.push_back(P(v, u));
    }
    //ここまでで作る回文の最短の長さをいれる配列
    vector<vector<int>> LEN_up_to_here(N, vector<int>(N, inf));
    LEN_up_to_here[0][N - 1] = 0;
    //この queue に次に見ていく始点と終点の組を入れる
    queue<P> que;
    que.push(P(0, N - 1));
    //次に見る始点と終点の組がなくなるまで
    //始点終点両方から幅優先探索をするイメージ
    //（既にみたものは書き換える必要がないね）
    while (!que.empty())
    {
        //queue の先頭を見る
        P now = que.front();
        que.pop();
        auto [start, goal] = now;
        for (int i = 0; i < 26; i++)
        {
            //start と goal からそのアルファベットの辺が生えているときを考える
            if (Graph[i][start].size() == 0 || Graph[i][goal].size() == 0)
            {
                continue;
            }
            for (auto to0 : Graph[i][start])
            {
                for (auto to1 : Graph[i][goal])
                {
                    if (LEN_up_to_here[to0][to1] != inf)
                    {
                        continue;
                    }
                    //回文の長さは 2 づつ増えるよね（両端から作っていくので）
                    LEN_up_to_here[to0][to1] = LEN_up_to_here[start][goal] + 2;
                    que.push(P(to0, to1));
                }
            }
        }
    }
    int ans = inf;
    //回文ができたよ～～うれしいね
    for (int i = 0; i < N; i++)
    {
        ans = min(ans, LEN_up_to_here[i][i]);
    }
    //あと一文字真ん中に入れたら回文になるよ～～
    for (int i = 0; i < 2 * M; i++)
    {
        auto [start, goal] = edges[i];
        ans = min(ans, LEN_up_to_here[start][goal] + 1);
    }
    // ans==inf となっている時は構築できない時と同値だよね～～（作れるときは inf 未満になるようにしたので）
    if (ans != inf)
    {
        cout << ans << endl;
        return 0;
    }
    cout << -1 << endl;
}
//計算量は幅優先探索以外は平気そう
//幅優先探索での計算量は実質的に
//頂点数 N*N, 辺 M*M とみなせるから、
//O(N*N+M*M)になる...タブンネ
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define N 1010
#define M 1010
#define ll long long
int last[N], nxt[M * 2], to[M * 2], ty[M * 2], len = 0;
int dis[N][N], p[N][N];
struct {
	int x, y;
}q[9000010];
void add(int x, int y, int w) {
	to[++len] = y;
	nxt[len] = last[x];
	ty[len] = w;
	last[x] = len;
}
int main() {
	int n, m, K, u, v, w, i, j, k;
	scanf("%d%d", &n, &m);
	memset(dis, 255, sizeof(dis));
	int l = 0, r = 0;
	for(i = 1; i <= m; i++) {
		char ch;
		scanf("%d%d %c", &u, &v, &ch);
		w = ch - 'a' + 1;
		add(u, v, w), add(v, u, w);
		dis[u][v] = dis[v][u] = 1;
		if(!p[u][v]) q[++r].x = u, q[r].y = v, p[u][v] = 1;
		if(!p[v][u]) q[++r].x = v, q[r].y = u, p[v][u] = 1;
	}
	for(i = 1; i <= n; i++) dis[i][i] = 0, p[i][i] = 1, q[++r].x = i, q[r].y = i;;
	while(l != r) {
		l = l % 9000005 + 1;
		u = q[l].x, v = q[l].y;
		for(i = last[u]; i; i = nxt[i]) {
			for(j = last[v]; j; j = nxt[j]) if(ty[j] == ty[i]) {
				if(dis[u][v] + 2 < dis[to[i]][to[j]] || dis[to[i]][to[j]] == -1) {
					dis[to[i]][to[j]] = dis[u][v] + 2;
					if(!p[to[i]][to[j]]) {
						r = r % 9000005 + 1;
						q[r].x = to[i], q[r].y = to[j];
						p[to[i]][to[j]] = 1;	
					}
				
				}
			}
		}
		p[u][v] = 0;
	}
	printf("%d\n", dis[1][n]);
	return 0;
}