#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); i++)
using namespace std;
using ll = long long;
using P = pair<int, int>;

const ll INF = 10e16;

int main() {
    int n, m;
    cin >> n >> m;
    vector<ll> a(m), b(m);
    vector<char> c(m);
    rep(i, m) {
        cin >> a[i] >> b[i] >> c[i];
        a[i]--, b[i]--;
    }

    vector<vector<vector<P>>> G(n, vector<vector<P>>(n));
    rep(i, m) rep(j, m) {
        if (i == j) continue;
        if (c[i] != c[j]) continue;
        G[a[i]][a[j]].push_back({b[i], b[j]});
        G[b[i]][b[j]].push_back({a[i], a[j]});
        G[a[i]][b[j]].push_back({b[i], a[j]});
        G[b[i]][a[j]].push_back({a[i], b[j]});
    }

    vector<vector<ll>> dist(n, vector<ll>(n, INF));
    queue<P> que;

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

    while (!que.empty()) {
        P p = que.front();
        que.pop();

        for (P np : G[p.first][p.second]) {
            if (dist[np.first][np.second] != INF) continue;
            dist[np.first][np.second] = dist[p.first][p.second] + 1;
            que.push(np);
        }
    }

    ll ans = INF;
    rep(i, n) ans = min(ans, dist[i][i] * 2);
    rep(i, m) {
        ans = min(ans, dist[a[i]][b[i]] * 2 + 1);
        ans = min(ans, dist[b[i]][a[i]] * 2 + 1);
    }

    if (ans == INF) ans = -1;
    cout << ans << endl;
}
#include <bits/stdc++.h>
using namespace std;

vector<pair<int,char>> adj[1000];
bool vis[1000][1000];
int best[1000][1000];

int main() {
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);

	int n, m;
	cin >> n >> m;

	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < n; ++j) {
			best[i][j] = 1e9;
		}
	}

	while (m--) {
		int u, v;
		char c;
		cin >> u >> v >> c, --u, --v;
		adj[u].emplace_back(v, c);
		adj[v].emplace_back(u, c);
	}

	best[0][n-1] = 0;
	queue<pair<int,int>> q;
	q.push({0, n-1});

	int ans = INT_MAX;

	while (!q.empty()) {
		int u, v;
		tie(u, v) = q.front();
		q.pop();
		if (vis[u][v]) continue;
		if (u == v) ans = min(ans, best[u][v]);
		vis[u][v] = true;
		for (auto [x1, c1] : adj[u]) {
			if (x1 == v) {
				ans = min(ans, best[u][v] + 1);
				continue;
			}
			for (auto [x2, c2] : adj[v]) {
				if (c1 == c2) {
					if (best[x1][x2] > best[u][v] + 2) {
						best[x1][x2] = best[u][v] + 2;
						q.push({x1, x2});
					}
				}
			}
		}
	}

	if (ans == INT_MAX) cout << "-1";
	else cout << ans;

	return 0;
}
