#include <bits/stdc++.h>
#define LL long long
#define ULL unsigned long long
#define pb push_back
#define st first
#define nd second
#define INF 0x3f3f3f3f
#define LINF 0x3f3f3f3f3f3f3f3f
template <class T> T read(T &a) {
    a=0;char x=getchar();bool f=0;
    for(;x<'0'||x>'9';x=getchar())f|=x=='-';
	for(;x>='0'&&x<='9';x=getchar())a=(a<<3)+(a<<1)+x-'0';
    if(f)a=-a;
    return a;
}
using namespace std;

const int N = 1e6 + 5;
int id[1005][1005];
typedef pair<int, int> tp;
vector<int> mp[1005][30];
int dis[N];
bool vis[N];
queue<int> q;
int f[N], nnext[N << 3], v[N << 3], cnt, cnt1;
int n, m;

void add(int a, int b) {
    nnext[++cnt] = f[a];
    f[a] = cnt;
    v[cnt] = b;
}


int main() {
    read(n), read(m);
    for (int i = 1; i <= m; ++i) {
        int a, b;
        char s[3];
        read(a), read(b);
        scanf("%s", s);
        mp[a][s[0] - 'a'].pb(b);
        mp[b][s[0] - 'a'].pb(a);
    }
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= n; ++j) {
            id[i][j] = ++cnt1;
        }
    }
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= n; ++j) {
            for (int k = 0; k < 26; ++k) {
                for (int I = 0; I < mp[i][k].size(); ++I) {
                    for (int J = 0; J < mp[j][k].size(); ++J) {
                        int x = mp[i][k][I], y = mp[j][k][J];
                        add(id[i][j], id[x][y]);
                    }
                }
            }
        }
    }
    int ans = INF;
    memset(dis, INF, sizeof dis);
    q.push(id[1][n]);
    dis[id[1][n]] = 0;
    vis[id[1][n]] = 1;
    while (!q.empty()) {
        int k = q.front();
        q.pop();
        vis[k] = 0;
        for (int i = f[k]; i; i = nnext[i]) {
            int to = v[i];
            if (dis[to] > dis[k] + 1) {
                dis[to] = dis[k] + 1;
                if (vis[to] == 0) {
                    vis[to] = 1;
                    q.push(to);
                }
            }
        }
    }
    for (int i = 1; i <= n; ++i) {
        if (dis[id[i][i]] != INF) ans = min(dis[id[i][i]] * 2, ans);
    }
    for (int i = 1; i <= n; ++i) {
        for (int j = 0; j < 26; ++j) {
            for (int k = 0; k < mp[i][j].size(); ++k) {
                int to = mp[i][j][k];
                if (dis[id[i][to]] != INF) {
                    ans = min(dis[id[i][to]] * 2 + 1, ans);
                }
            }
        }
    }
    if (ans == INF) puts("-1"); else cout << ans << endl;
	return 0;
}

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double

int main() {
    int N, M;
    cin >> N >> M;
    vector<int> A(M), B(M);
    vector<char> C(M);
    for (int i = 0; i < M; i++) {
        cin >> A[i] >> B[i] >> C[i];
        A[i]--;
        B[i]--;
    }
    vector<int> dist(N*N, 1e9);
    vector<int> visited(N*N, false);
    queue<int> q;
    for (int i = 0; i < N; i++) {
        dist[i*N+i] = 0;
        q.push(i*N+i);
        visited[i*N+i] = true;
    }
    vector<vector<int>> edge(N*N);
    for (int i = 0; i < M; i++) {
        if (dist[A[i]*N+B[i]] > 1) {
            dist[A[i]*N+B[i]] = 1;
            q.push(A[i]*N+B[i]);
        }
        if (dist[B[i]*N+A[i]] > 1) {
            dist[B[i]*N+A[i]] = 1;
            q.push(B[i]*N+A[i]);
        }
        visited[A[i]*N+B[i]] = true;
        visited[B[i]*N+A[i]] = true;
        for (int j = i+1; j < M; j++) {
            if (C[i] != C[j]) continue;
            edge[A[i]*N+A[j]].push_back(B[i]*N+B[j]);
            edge[A[j]*N+A[i]].push_back(B[j]*N+B[i]);
            edge[B[i]*N+B[j]].push_back(A[i]*N+A[j]);
            edge[B[j]*N+B[i]].push_back(A[j]*N+A[i]);
            
            edge[A[i]*N+B[j]].push_back(B[i]*N+A[j]);
            edge[A[j]*N+B[i]].push_back(B[j]*N+A[i]);
            edge[B[i]*N+A[j]].push_back(A[i]*N+B[j]);
            edge[B[j]*N+A[i]].push_back(A[j]*N+B[i]);
        }
    }
    while (!q.empty()) {
        int now = q.front();
        q.pop();
        for (int nxt : edge[now]) {
            if (dist[nxt] <= dist[now]+2) continue;
            dist[nxt] = dist[now]+2;
            visited[nxt] = true;
            q.push(nxt);
        }
    }
    if (dist[N-1] >= 1e8) cout << -1 << endl;
    else cout << dist[N-1] << endl;
    return 0;
}