// 2021-03-28 11:22:37
// clang-format off
#include <bits/stdc++.h>
#ifdef LOCAL
#include "lib/debug.hpp"
#else
#define debug(...) 1
#endif
#define ALL(a) (a).begin(), (a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define rep(i, n) REP(i, 0, (n))
#define repc(i, n) REPC(i, 0, (n))
#define REP(i, n, m) for (int i = (int)(n); i < (int)(m); i++)
#define REPC(i, n, m) for (int i = (int)(n); i <= (int)(m); i++)
#define REPCM(i, n, m) for (int i = (int)(n); i >= (int)(m); i--)
template<class T> inline bool chmin(T& a, const T& b) { if (a > b) { a = b; return true; } else return false; }
template<class T> inline bool chmax(T& a, const T& b) { if (a < b) { a = b; return true; } else return false; }
using namespace std;
using ll = long long;
using ld = long double;
using P = pair<int, int>;

// clang-format on
const int MX = 1010, inf = 1e9;
bool A[MX][MX];
int dist[MX][MX];
vector<int> G[MX][26];
using T = tuple<int, int, int>;
void answer() {
  int n, m;
  cin >> n >> m;
  rep(i, m) {
    int a, b, c;
    char c_;
    cin >> a >> b >> c_;
    a--;
    b--;
    c = c_ - 'a';
    A[a][b] = A[b][a] = true;
    G[a][c].push_back(b);
    G[b][c].push_back(a);
  }
  rep(i, n) rep(j, n) dist[i][j] = inf;
  dist[0][n - 1] = 0;
  int ans = inf;
  queue<T> que;
  que.emplace(0, n - 1, 0);
  while (!que.empty()) {
    auto [x, y, cost] = que.front();
    que.pop();
    if (dist[x][y] < cost) continue;
    if (x == y) {
      chmin(ans, cost * 2);
      continue;
    }
    if (A[x][y]) {
      chmin(ans, cost * 2 + 1);
      continue;
    }
    rep(z, 26) {
      for (auto x2 : G[x][z]) {
        for (auto y2 : G[y][z]) {
          int u = min(x2, y2);
          int v = max(x2, y2);
          if (dist[u][v] <= cost + 1) continue;
          dist[u][v] = cost + 1;
          que.emplace(u, v, cost + 1);
        }
      }
    }
  }
  if (ans == inf) ans = -1;
  cout << ans << '\n';
}

int main() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(0);
  answer();
  return 0;
}
//12252024832524
#include <queue>
#include <cstdio>
#include <vector>
#include <cstring>
#include <algorithm>
#define TT template<typename T>
using namespace std;

typedef long long LL;
const int MAXN = 1005;
int n,m;
int vis[MAXN][MAXN],woc[MAXN][MAXN];

LL Read()
{
	LL x = 0,f = 1;char c = getchar();
	while(c > '9' || c < '0'){if(c == '-')f = -1;c = getchar();}
	while(c >= '0' && c <= '9'){x = (x*10) + (c^48);c = getchar();}
	return x * f;
}
TT void Put1(T x)
{
	if(x > 9) Put1(x/10);
	putchar(x%10^48);
}
TT void Put(T x,char c = -1)
{
	if(x < 0) putchar('-'),x = -x;
	Put1(x); if(c >= 0) putchar(c);
}
TT T Max(T x,T y){return x > y ? x : y;}
TT T Min(T x,T y){return x < y ? x : y;}
TT T Abs(T x){return x < 0 ? -x : x;}

vector<int> E[30][MAXN];
void Add_Edge(int x,int y,int z)
{
    E[z][x].push_back(y);
}
void Add_Double_Edge(int x,int y,int z)
{
    vis[x][y] = vis[y][x] = z;
    Add_Edge(x,y,z);
    Add_Edge(y,x,z);
}
int gc()
{
    char c = getchar();
    while(c > 'z' || c < 'a'){c = getchar();}
    return c - 'a' + 1;
}
struct node
{
    int s,t,dis;
    node(){}
    node(int s1,int t1,int dis1){
        s = s1;
        t = t1;
        dis = dis1;
    }
};

int bfs()
{
    queue<node> q;
    q.push(node(1,n,0));
    woc[1][n] = 1;
    while(!q.empty())
    {
        node w = q.front(); q.pop();
        if(vis[w.s][w.t]) return w.dis * 2 + 1;
        for(int i = 1;i <= 26;++ i)
        {
            for(int j = 0,len1 = E[i][w.s].size();j < len1;++ j)
                for(int k = 0,len2 = E[i][w.t].size();k < len2;++ k)
                {
                    int tox = E[i][w.s][j],toy = E[i][w.t][k];
                    if(!woc[tox][toy])
                    {
                        woc[tox][toy] = 1;
                        if(tox == toy) return w.dis*2+2;
                        q.push(node(tox,toy,w.dis+1));
                    }
                }
        }
    }
    return -1;
}

int main()
{
//	freopen(".in","r",stdin);
//	freopen(".out","w",stdout);
    n = Read(); m = Read();
    for(int i = 1;i <= m;++ i)
    {
        int u = Read(),v = Read();
        Add_Double_Edge(u,v,gc());
    }
    Put(bfs());
	return 0;
}
