#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;
}

#include<bits/stdc++.h>

#define fox(i,a,b) for(int i=a;i<=b;++i)
#define ll long long

using namespace std;

int _x, _f; char _c;
inline int rd() {
	_x = 0, _f = 1, _c = getchar();
	for (; !isdigit(_c); _c = getchar()) if (_c == '-') _f = 0;
	for (; isdigit(_c); _c = getchar()) _x = _x * 10 + _c - '0';
	return _f ? _x : -_x;
}

const int N = 1010;
int n, m, g = INT_MAX;
struct edge { vector<int>tr[26];} e[N];
bool ud[N][N], lt[N][N];

struct nwp { int x, y, st;};
queue<nwp> q;

signed main() {
	n = rd(), m = rd();
	int x, y; char c;
	fox (i, 1, m) {
		x = rd(), y = rd();
		lt[x][y] = lt[y][x] = 1;
		scanf("%c", &c);
		e[x].tr[c-'a'].push_back(y);
		e[y].tr[c-'a'].push_back(x); 
	}
	
	nwp a, b;
	a.x = 1, a.y = n, a.st = 0;
	if (lt[1][n]) {
		puts("1");
		return 0;
	}
	q.push(a);
	while (!q.empty()) {
		a = q.front(), q.pop();
		if (ud[x = a.x][y = a.y]) continue;
		ud[x][y] = 1;
		b.st = a.st + 1;
		if (b.st * 2 > g) {
			printf("%d\n", g);
			return 0;
		}
		fox (i, 0, 25) {
			for (int j = 0; j < e[x].tr[i].size(); ++j){
				for (int k = 0; k < e[y].tr[i].size(); ++k){
					b.x = e[x].tr[i][j], b.y = e[y].tr[i][k];
					if (b.x == b.y) {
						printf("%d\n", b.st * 2);
						return 0;
					}
					if (lt[b.x][b.y]) g = b.st * 2 + 1;
					if (ud[b.x][b.y]) continue;
					q.push(b);
				}
			}
		}
	} puts("-1");
	return 0;
}
