#include <bits/stdc++.h>
#define REP(i, s, n) for (int i = s; i < (int)(n); i++)
#define ALL(a) a.begin(), a.end()
#define MOD 1000000007
using namespace std;
using ll = long long;

int main() {
    int N, M; cin >> N >> M;
    vector<vector<vector<int>>> G(N, vector<vector<int>>(26));
    vector<vector<bool>> adj(N, vector<bool>(N, false));
    REP(i, 0, M) {
        int a, b; char c; cin >> a >> b >> c; a--; b--; c -= 'a';
        G[a][c].push_back(b);
        G[b][c].push_back(a);
        adj[a][b] = adj[b][a] = true;
    }

    int ans = 1 << 30;
    queue<pair<int, int>> Q;
    Q.push({0, N - 1});
    vector<vector<int>> dist(N, vector<int>(N, -1));
    dist[0][N - 1] = dist[N - 1][0] = 0;

    while (!Q.empty()) {
        auto [u, v] = Q.front(); Q.pop();
        if (ans <= dist[u][v]) break;
        if (u == v) {
            ans = min(ans, 2 * dist[u][v]);
            continue;
        }
        if (adj[u][v]) {
            ans = min(ans, 2 * dist[u][v] + 1);
            continue;
        }
        REP(i, 0, 26) {
            for (auto x : G[u][i]) {
                for (auto y : G[v][i]) {
                    if (dist[x][y] != -1) continue;
                    dist[x][y] = dist[y][x] = dist[u][v] + 1;
                    Q.push({x, y});
                }
            }
        }
    }
    if (ans < (1 << 30)) cout << ans << endl;
    else cout << -1 << endl;

    return 0;
}

#include<bits/stdc++.h>
#define maxn 1005
using namespace std;
vector<int> edge[1005][26];
int dp[1001][1001][27];
int mp[1001][1001];
int n,m;
int u,v; char c;
struct nod{
	int u,v,c;
	nod() {}
	nod(int x,int y,int z) {u=x; v=y; c=z;}
};
nod q[27000005];
int head,tail;
void bfs()
{
	dp[1][n][26]=1;
	head=tail=1; q[1]=nod(1,n,26);
	while (head<=tail)
	{
		nod tt=q[head++];
		int u,v,c;
		u=tt.u; v=tt.v; c=tt.c;
//		cout<<u<<" "<<v<<" "<<c<<" "<<dp[u][v][c]<<endl;
		if (c!=26)
		{
			int siz=edge[v][c].size();
			for (int j=0;j<siz;j++)
			{
				int temp=edge[v][c][j];
				if (dp[u][temp][26]==0)
				{
					dp[u][temp][26]=dp[u][v][c]+1;
					q[++tail]=nod(u,temp,26);
				}
			}
		}
		else
		{
			for (int o=0;o<=25;o++)
			{
				int siz=edge[u][o].size();
				for (int j=0;j<siz;j++)
				{
					int temp=edge[u][o][j];
					if (dp[temp][v][o]==0)
					{
						dp[temp][v][o]=dp[u][v][c]+1;
						q[++tail]=nod(temp,v,o);
					}
				}
			}
		}
	}
	long long ans=99999999;
	for (int i=1;i<=n;i++)
	if (dp[i][i][26]!=0)
	{
		ans=min(ans,dp[i][i][26]-1ll);
	}
	for (int i=1;i<=n;i++)
	for (int j=1;j<=n;j++)
	if (dp[i][j][26]!=0 && mp[i][j]==1)
	{
		ans=min(ans,dp[i][j][26]+0ll);
	}
	if (ans==99999999) cout<<-1<<endl; else cout<<ans<<endl;
	return;
}

int main()
{
	cin>>n>>m;
	for (int i=1;i<=m;i++)
	{
		cin>>u>>v>>c;
		int C=c-='a';
		edge[u][C].push_back(v);
		edge[v][C].push_back(u);
		mp[u][v]=mp[v][u]=1;
	}
	bfs();
}
