#include <bits/stdc++.h>

using namespace std;

#define int long long

const int N = 1050;

vector<int> g[N][26];
bool vis[N][N];
int dp[N][N];


signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

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

    for (int i = 0; i < m; i++) {
        int a, b;
        char c;
        cin >> a >> b >> c;

        g[a][c - 'a'].push_back(b);
        g[b][c - 'a'].push_back(a);
    }

    fill(&dp[0][0], &dp[n + 1][0], LLONG_MAX);

    queue<pair<int, int> > bfs;
    for (int i = 1; i <= n; i++) {
        bfs.emplace(i, i);
        vis[i][i] = true;
        dp[i][i] = 0;
    }

    for (int i = 1; i <= n; i++) {
        for (int j = 0; j < 26; j++) {
            for (auto to: g[i][j]) {
                if (vis[i][to])
                    continue;
                bfs.emplace(i, to);
                vis[i][to] = vis[to][i] = true;
                dp[i][to] = dp[to][i] = 1;
            }
        }
    }

    while (!bfs.empty()) {
        pair<int, int> nodes = bfs.front();
        bfs.pop();
        int u = nodes.first;
        int v = nodes.second;

        for (int j = 0; j < 26; j++) {
            for (auto nu: g[u][j]) {
                for (auto nv: g[v][j]) {
                    if (vis[nu][nv])
                        continue;
                    vis[nu][nv] = vis[nv][nu] = true;
                    dp[nu][nv] = dp[nv][nu] = dp[u][v] + 2;
                    bfs.emplace(nu, nv);
                }
            }
        }
    }
    cout << (dp[1][n] == LLONG_MAX ? -1 : dp[1][n]);


}



#pragma GCC optimize("O3")
#pragma GCC target("sse4")

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef unsigned int uint;
typedef pair<int, int> pii;

typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<pii> vpii;

#define FOR(i, a, b) for (int i = a; i <= (b); i++)
#define F0R(i, a) for (int i = 0; i < (a); i++)
#define FORd(i, a, b) for (int i = (b); i >= a; i--)
#define F0Rd(i, a) for (int i = (a)-1; i >= 0; i--)
#define trav(a, x) for (auto &a : x)

#define sz(x) (int)(x).size()
#define popcnt(x) __builtin_popcount(x)
#define low_bo(a, x) (lower_bound(a.begin(), a.end(), x) - a.begin())
#define up_bo(a, x) (upper_bound(a.begin(), a.end(), x) - a.begin())
#define unique(a) a.resize(unique(a.begin(), a.end()) - a.begin())
#define shuffle(a) shuffle(a.begin(), a.end(), rnd)
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define f first
#define s second
#define lb lower_bound
#define ub upper_bound
#define all(x) x.begin(), x.end()
#define ins insert

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const int MOD = 1000000007;
const char nl = '\n';
const int MX = 150001; //check the limits, dummy
set<pii> visited;
void solve(int t) {
  int n, m;
  cin>>n >> m;
  map<int, map<int, char>> adj;
  F0R(i,m) {
    int u,v;
    char c;
    cin>>u>>v>>c;
    u--, v--;
    adj[u][v]=c;
    adj[v][u]=c;
  }
  // negative length of string
  priority_queue<pair<ll, pii>> pq;
  pq.push(mp(0,mp(0,n-1)));
  int u,v;
  set<int> pos;
  while(!pq.empty()) {
    auto cur = pq.top();
    pq.pop();
    ll l = -cur.f;
    tie(u,v) = cur.s;
    // cout << l <<" "<<st<<" "<<u<<" "<<v<<nl;
    if(visited.find({u,v})!=visited.end()) {
      // cout << "hi\n";
      continue;
    }
    visited.ins({u,v});
    if(u==v) {
      pos.ins(2*l);
      // cout << 2*l<<nl;
      // return;
    }
    if(adj[u].find(v)!=adj[u].end()) {
      pos.ins(2*l+1);
      // cout << 2*l+1<<nl;
      // return;
    }
    for(auto au : adj[u]) {
      for(auto av : adj[v]) {
        if(au.s==av.s) {
          pq.push(mp(-l-1,mp(au.f,av.f)));
        }
      }
    }
  }
  if(!pos.empty()) cout << *(pos.begin())<<nl;
  else
  cout << "-1\n";
}

int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  cout.precision(20);
  cout << fixed;
  
  int T = 1;
  F0R(i,T) {
    solve(i+1);
  }
}

// read the question correctly (ll vs int)
// template by bqi343