#include <algorithm>
#include <cstdio>
#include <functional>
#include <iostream>
#include <cfloat>
#include <climits>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <time.h>
#include <complex>
#include <vector>
#include <limits>
#include <iomanip>
#include <cassert>
#include <numeric>
#include <chrono>
#include <random>

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

#define debug(x) cerr << #x << " = " << (x) << endl;
#define debug_pii(x) cerr << "(" << x.first << "," << x.second << ")";
#define rep(i, n) for(int i = 0;i < n;i++)
#define pb push_back
#define F first
#define S second

// template<typename _Ty1, typename _Ty2>
// ostream& operator<<(ostream& _os, const pair<_Ty1, _Ty2>& _p) {
//     _os << '(' <<_p.first << ',' << _p.second << ')';
//     return _os;
// }
//
// template<typename _Ty1, typename _Ty2>
// istream& operator>>(istream& _is, pair<_Ty1, _Ty2>& _p) {
//     _is >> _p.first >> _p.second;
//     return _is;
// }

const int nmax = 1000;
bool g[nmax][nmax][26];
int n,m,a,b;char c;
bool visited[nmax][nmax];
int dist[nmax][nmax];
vector<pii> gg[nmax];

int bfs(int s,int e) {
  queue<pii> q;
  q.push({s,e});
  visited[s][e] = true;
  int ans = INT_MAX;
  while (!q.empty()) {
    pii v = q.front();
    q.pop();
    if(v.F == v.S) {
      ans=min(ans, dist[v.F][v.S]);
      continue;
    }
    bool chk = false;
    rep(i,26) {
      if(g[v.F][v.S][i]) {
        ans=min(ans, dist[v.F][v.S]+1);
        chk=true;
        break;
      }
    }
    if(chk) continue;
    s = v.F,e = v.S;
    for(int i = 0;i < gg[s].size();i++) {
      for(int j = 0;j < gg[e].size();j++) {
        if(gg[s][i].S != gg[e][j].S) continue;
        if(gg[s][i].F == s && gg[e][j].F == e) continue;
        if(!visited[gg[s][i].F][gg[e][j].F]) {
          visited[gg[s][i].F][gg[e][j].F]=true;
          q.push({gg[s][i].F,gg[e][j].F});
          dist[gg[s][i].F][gg[e][j].F]=dist[s][e]+2;
        }
      }
    }
  }

  return (ans == INT_MAX?-1:ans);
}

void solve() {
  cin>>n>>m;
  rep(i,m){
    cin>>a>>b>>c;
    a--;b--;
    g[a][b][c-'a']=g[b][a][c-'a']=1;
    gg[a].pb({b,c-'a'});
    gg[b].pb({a,c-'a'});
  }
  cout << bfs(0, n-1) << endl;
}

// 2 10 5 15 30
// ABABABA A

int main() {

 // freopen("input.in","r",stdin);
 // freopen("output.out","w",stdout);
 // cout << fixed << setprecision(15);

 ios_base::sync_with_stdio(false);
 cin.tie(nullptr);

 int t = 1;
 // cin >> t;
 while (t--) {
   solve();
 }

 return 0;
}

#include <bits/stdc++.h>
#define F first
#define S second
using namespace std;
typedef long long ll;
vector<int> v[1000][26];
int n,m,a,b,c,d[1000][1000];
char cha;
string s;
queue<int> que;
int main(void){
    cin>>n>>m;
    for(int i=0;i<n;i++){
        que.push(i*1000+i);
        for(int j=0;j<n;j++){
            if(i!=j)d[i][j]=(1<<30);
        }
    }
    for(int i=0;i<m;i++){
        cin>>a>>b>>cha;
        a--,b--;
        v[a][cha-'a'].push_back(b);
        if(a!=b)v[b][cha-'a'].push_back(a);
        if(a!=b){
            d[a][b]=1;
            d[b][a]=1;
            que.push(1000*a+b);
        }
    }
    while(que.size()){
        a=que.front()/1000;
        b=que.front()%1000;
        que.pop();
        if(abs(b-a)==n-1){
            cout<<d[a][b]<<endl;
            return 0;
        }
        for(int i=0;i<26;i++){
            for(auto x:v[a][i]){
                for(auto y:v[b][i]){
                    if(d[x][y]>d[a][b]+2){
                        d[x][y]=d[a][b]+2;
                        que.push(x*1000+y);
                    }
                }
            }
        }
    }
    cout<<-1<<endl;
}

