#include<bits/stdc++.h>

using namespace std;
typedef long long ll;

#define rep(i,n) for (long long i = 0; i < (n); ++i)
#define DIV 1000000007 //10^9+7
#define INF 1000000007 //10^9+7

template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }
int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};

vector<pair<ll, ll> > to[1005];
ll memo[1005][1005];


int main(){
	ll N, M;
	cin >> N >> M;

	rep(i, M) {
		char ch;
		ll a, b, c;
		cin >> a >> b >> ch;
		c = ch-'a';
		a--;b--;
		to[a].push_back(make_pair(b, c));
		to[b].push_back(make_pair(a, c));
	}

	ll ret = INF;
	rep(i, N) rep(j, N) memo[i][j] = -1;

	//cost, s, e
	priority_queue<tuple<ll, ll, ll>, vector<tuple<ll, ll, ll> >, greater<tuple<ll,ll,ll>>>Q;

	Q.push({0, 0, N-1});

	while(!Q.empty()) {
		ll cost, s, e;
		tie(cost, s, e) = Q.top();
		Q.pop();
		if(memo[s][e] != -1) continue;
		memo[s][e] = cost;

		if(s == e) {
			chmin(ret, cost);
			continue;
		}

		for(auto item0: to[s]) if(item0.first == e) {
			chmin(ret, cost + 1);
			continue;
		}

		for(auto item0: to[s]) for(auto item1: to[e]) {
			if(item0.second == item1.second) {
				Q.push({cost + 2, item0.first, item1.first});
			}
		}
	}
	if(ret != INF) {
		cout << ret << endl;
		return 0;
	}

	cout << -1 << endl;
}


// atcoder/abc197/F/main.cpp
// author: @___Johniel
// github: https://github.com/johniel/

#include <bits/stdc++.h>

#define each(i, c) for (auto& i : c)
#define unless(cond) if (!(cond))

using namespace std;

template<typename P, typename Q> ostream& operator << (ostream& os, pair<P, Q> p) { os << "(" << p.first << "," << p.second << ")"; return os; }
template<typename P, typename Q> istream& operator >> (istream& is, pair<P, Q>& p) { is >> p.first >> p.second; return is; }
template<typename T> ostream& operator << (ostream& os, vector<T> v) { os << "("; for (auto& i: v) os << i << ","; os << ")"; return os; }
template<typename T> istream& operator >> (istream& is, vector<T>& v) { for (auto& i: v) is >> i; return is; }
template<typename T> ostream& operator << (ostream& os, set<T> s) { os << "#{"; for (auto& i: s) os << i << ","; os << "}"; return os; }
template<typename K, typename V> ostream& operator << (ostream& os, map<K, V> m) { os << "{"; for (auto& i: m) os << i << ","; os << "}"; return os; }

template<typename T> inline T setmax(T& a, T b) { return a = std::max(a, b); }
template<typename T> inline T setmin(T& a, T b) { return a = std::min(a, b); }

using lli = long long int;
using ull = unsigned long long;
using point = complex<double>;
using str = string;
template<typename T> using vec = vector<T>;

constexpr array<int, 8> di({0, 1, -1, 0, 1, -1, 1, -1});
constexpr array<int, 8> dj({1, 0, 0, -1, 1, -1, -1, 1});
constexpr lli mod = 1e9 + 7;

const int N = 1000 + 3;
vec<pair<int, char>> g[N];


int main(int argc, char *argv[])
{
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.setf(ios_base::fixed);
  cout.precision(15);

  int n, m;
  while (cin >> n >> m) {
    fill(g, g + N, vec<pair<int, char>>());
    for (int i = 0; i < m; ++i) {
      int a, b;
      char c;
      cin >> a >> b >> c;
      --a;
      --b;
      g[a].push_back(make_pair(b, c));
      g[b].push_back(make_pair(a, c));
    }

    const int inf = 1 << 29;
    static int cost[N][N];
    fill(&cost[0][0], &cost[N - 1][N - 1] + 1, inf);
    cost[0][n - 1] = 0;
    priority_queue<pair<int, pair<int, int>>> q;
    q.push(make_pair(0, make_pair(0, n - 1)));
    while (q.size()) {
      auto p = q.top();
      q.pop();
      int c = abs(p.first);
      int a = p.second.first;
      int b = p.second.second;
      map<char, vec<int>> x, y;
      each (i, g[a]) x[i.second].push_back(i.first);
      each (i, g[b]) y[i.second].push_back(i.first);
      for (char d = 'a'; d <= 'z'; ++d) {
        each (i, x[d]) {
          each (j, y[d]) {
            int nc = c + 2;
            if (cost[i][j] > nc) {
              cost[i][j] = nc;
              q.push(make_pair(-nc, make_pair(i, j)));
            }
          }
        }
      }
    }
    int mn = inf;
    for (int i = 0; i < N; ++i) {
      setmin(mn, cost[i][i]);
    }
    for (int i = 0; i < n; ++i) {
      each (e, g[i]) {
        int j = e.first;
        setmin(mn, cost[i][j] + 1);
      }
    }
    cout << (mn == inf ? -1 : mn) << endl;
  }

  return 0;
}
