/*
Alexander Rango
*/
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define endl                        '\n'
#define pii pair <ll , ll>
#define F first
#define S second
const ll max_n = 1e3 + 20, inf = 1e18 + 20;
ll dist[max_n][max_n], n, m ,s, t, T, u, v, w, ans;
char c;
bitset <max_n> visited[max_n];
vector <pii> g[max_n][26];
void solve(ll x, ll y) {
    for (ll i = 1; i <= n; i++) {
    	fill(dist[i] + 1, dist[i] + n + 1, inf);
		visited[i] = 0;
	} 
    dist[x][y] = 0;
    priority_queue < pair <ll , pii > > pq;
    pq.push({0, {x, y}});
    while (!pq.empty()) {
        ll x = pq.top().S.F;
		ll y = pq.top().S.S;
		pq.pop();
        if (!visited[x][y]) {
        	visited[x][y] = 1;
        	for (ll i = 0; i < 26; i++) {
        		for (pii u : g[x][i]) {
        			for (pii v : g[y][i]) {
        				if (dist[x][y] + u.S + v.S < dist[u.F][v.F]) {
        					dist[u.F][v.F] = dist[x][y] + u.S + v.S;
							pq.push({-dist[u.F][v.F], {u.F, v.F}});
						}
					}
				}
			}
		}
    }
}
int main() {
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    // cin >> T;
    T = 1;
    while (T--) {
        cin >> n >> m/* >> s >> t*/;
    	for(ll i = 1; i <= n; i++) {
    		for (ll j = 0; j < 26; j++) {
    			g[i][j].clear();
			}
		}
    	for(ll i = 0; i < m; i++) {
       	 	cin >> u >> v /*>> w*/ >> c;
       	 	g[u][int(c) - 97].push_back({v, 1});
       		g[v][int(c) - 97].push_back({u, 1});
    	}
        ans = inf;
        solve(1, n);
        for (ll i = 1; i <= n; i++) {
            ans = min(ans, dist[i][i]);
        }
        for (ll u = 1; u <= n; u++) {
            for (ll j = 0; j < 26; j++) {
                for (pii v : g[u][j]) {
                    ans = min(ans, dist[u][v.F] + v.S);
                }
            }
        }
        if(ans == inf)ans = -1;
		cout << ans << endl;
   	}
    return 0;
}


#include <bits/stdc++.h>
#define FAST ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
typedef long long ll;
typedef long double ld;
#define pb push_back
#define mp make_pair
#define ff first
#define ss second
#define mod 1000000007
#define pii pair<ll,ll>
#define inf 1000000000000000000
#define bpc(x) __builtin_popcountll(x)
#define autoit(x,it) for(auto it = x.begin(); it != x.end(); it++)
#define autoitr(x,it) for(auto it = x.rbegin(); it != x.rend(); it++)
#define rep(n) for(ll i = 0; i < n; i++)
#define repi(i,n) for(ll i = 0; i < n; i++)

#include <ext/pb_ds/assoc_container.hpp> 
#include <ext/pb_ds/tree_policy.hpp> 
using namespace __gnu_pbds; 

#define ordered_set tree<ll, null_type,less<ll>, rb_tree_tag,tree_order_statistics_node_update> 

using namespace std;
mt19937_64 mt(chrono::steady_clock::now().time_since_epoch().count());

void get(ll i, ll arr[], ll n, ll xo, ll o, ll &ans)
{
    if(i == n)
    {
        ans = min(ans, xo^o);
        return;
    }
    
    get(i+1, arr, n, xo, o|arr[i], ans);
    get(i+1, arr, n, xo^o, arr[i], ans);
}

const ld PI = acos(-1);

ll n;
ll get(ll i, ll j)
{
    return i*n + j;
}

void dijk(vector<ll> v[], ll n, ll x, vector<ll> &dis)
{
    dis[x] = 0;
    queue<pii> q;
    q.push(mp(0,x));
    dis[x] = 0;
    
    while(q.size() > 0)
    {
        ll temp = q.front().second;
        q.pop();
        
        for(auto it = v[temp].begin();it!=v[temp].end();it++)
        {
            ll v1 = *it;
            ll wt = 1;
            
            if(dis[v1]>dis[temp] + wt)
            {
                dis[v1] = dis[temp] + wt;
                q.push({dis[v1],v1});
            }
        }
    }
  
}

int main()
{
  FAST/**/
  
  ll m;
  cin>>n>>m;
  
  vector<pii> gr[n];
  bool ter = 0;
  rep(m)
  {
      ll a,b;
      char c;
      cin>>a>>b>>c;
      a--, b--;
      if(a>b)
            swap(a,b);
      if(a == 0 && b == n-1 && ter == false)
      {
          cout<<1<<'\n';
          ter = true;
      }
      gr[a].pb({b,c});
      gr[b].pb({a,c});
  }
  
  if(ter)
    return 0;
  
  ll lim = n*n;
  vector<ll> tot[lim];
  for(ll i=0;i<n;i++)
  {
      for(ll j=0;j<n;j++)
      {
          autoit(gr[i],it)
                autoit(gr[j],it1)
                {
                    if(it1->ss == it->ss)
                        tot[get(i,j)].pb(get(it->ff, it1->ff));
                }
      }
  }
  vector<ll> dis(lim,inf);
  dijk(tot,lim,get(0,n-1),dis);
  
  ll ans = inf;
  rep(n)
        ans = min(ans, 2*dis[get(i,i)]);
  rep(n)
        autoit(gr[i],it)
        {
            ans = min(ans, 1 + 2*dis[get(i,it->ff)]);
        }
  if(ans == inf)
        ans = -1;
  cout<<ans<<"\n";        
  
  
  return 0;
}
   
   
 