#include <bits/stdc++.h>

using namespace std;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  int N, M;
  cin >> N >> M;
  vector<vector<int>> dist(N, vector<int>(N, -1));
  queue<pair<int, int>> que;
  for (int i = 0; i < N; i++) {
    dist[i][i] = 0;
    que.push(make_pair(i, i));
  }
  vector<vector<pair<int, int>>> G(N);
  for (int i = 0; i < M; i++) {
    int u, v;
    cin >> u >> v;
    char c;
    cin >> c;
    u--, v--;
    G[u].emplace_back(make_pair(v, c - 'a'));
    G[v].emplace_back(make_pair(u, c - 'a'));
    if (dist[u][v] < 0) {
      dist[u][v] = 1;
      que.push(make_pair(u, v));
    }
    if (dist[v][u] < 0) {
      dist[v][u] = 1;
      que.push(make_pair(v, u));
    }
  }
  while (!que.empty()) {
    auto [x, y] = que.front();
    que.pop();
    for (const auto &a : G[x]) {
      for (const auto &b : G[y]) {
        if (a.second == b.second) {
          if (dist[a.first][b.first] < 0) {
            dist[a.first][b.first] = dist[x][y] + 2;
            que.push(make_pair(a.first, b.first));
          }
        }
      }
    }
  }
  cout << dist[0][N - 1] << '\n';
  return 0;
}

#include <bits/stdc++.h>
#define REP(i,n) for(int i=0;i<(int)(n);++i)
#define ALL(v)   (v).begin(),(v).end()
#define debug(x) cerr<<#x<<": "<<(x)<<endl
using namespace std;
using llong = long long;
using vi    = vector<int>;
using vvi   = vector<vi >;
using vvvi  = vector<vvi >;
using pii   = pair<int,int>;
constexpr int    INF  = 1e9;
constexpr llong  LINF = 1e18;
constexpr double EPS  = 1e-12;
constexpr int    MOD  = 1e9+7;
template<class Type>
void line(const Type &a){int cnt=0;for(const auto &elem:a)cerr<<(cnt++?' ':'>')<<elem;cerr<<endl;}

/*ダイクストラ法*/
template<typename T>
class Dijkstra{
	using P=std::pair<T,int>;
	struct Edge{						//Edge:辺の情報を表す構造体.
		int to;
		T cost;
	};
	
	int vn;								//vn:=(ノード数).
	std::vector<std::vector<Edge> > g;	//g[v]:=(ノードvがもつ辺のリスト).
	std::vector<T> d;					//d[v]:=(ノードsからvへの最短距離).
	std::vector<int> pre;				//pre:=(逆方向経路（経路復元用）).
	T inf;
	
public:
	//constructor.
	Dijkstra():Dijkstra(0){}
	Dijkstra(size_t vn_,T inf_=1e9):vn(vn_),g(vn_),d(vn_,inf_),pre(vn_,-1),inf(inf_){}
	
	int get_vn() const{return vn;}
	T get_inf() const{return inf;}
	void add_edge(int from,int to,T cost){//重み付き有向辺を張る.
		assert(0<=from and from<vn);
		assert(0<=to and to<vn);
		g[from].push_back((Edge){to,cost});
	}
	void dijkstra(int s){//sから各ノードへの最短距離を求める. O(|E|log|V|).
		assert(0<=s and s<vn);
		std::fill(d.begin(),d.end(),inf);
		d[s]=0;
		std::fill(pre.begin(),pre.end(),-1);
		std::priority_queue<P,std::vector<P>,std::greater<P> > pque;
		pque.emplace(0,s);
		while(!pque.empty()){
			auto [cost,v]=pque.top();
			pque.pop();
			if(d[v]<cost) continue;
			for(const Edge &e:g[v]){
				if(d[e.to]>d[v]+e.cost){
					d[e.to]=d[v]+e.cost;
					pre[e.to]=v;
					pque.emplace(d[e.to],e.to);
				}
			}
		}
	}
	T dist(int t) const{//ノードsからtへの最短距離を返す.
		assert(0<=t and t<vn);
		return d[t];
	}
	std::vector<int> get_path(int t) const{//ノードtへの最短経路を返す.
		assert(0<=t and t<vn);
		std::vector<int> path;
		for(;t!=-1;t=pre[t]) path.push_back(t);
		std::reverse(path.begin(),path.end());
		return path;
	}
};

int main(){
	int n,m;
	cin>>n>>m;
	
	vvvi g(n,vvi(26));//g[v][c]:=(vがもつ文字cが書かれる辺のリスト).
	REP(i,m){
		int a,b;
		char c;
		cin>>a>>b>>c;
		a--, b--;
		
		g[a][c-'a'].push_back(b);
		g[b][c-'a'].push_back(a);
	}
	
	map<pii,int> mp;//グラフのノード番号参照用.
	int vn=0;
	REP(i,n)for(int j=i;j<n;++j) mp[pii(i,j)]=vn++;
	
	Dijkstra<llong> ob(vn,LINF);
	int s=mp[pii(0,n-1)], t=vn-1;
	REP(i,n) ob.add_edge(mp[pii(i,i)],t,0);
	REP(i,n)REP(c,26)for(auto j:g[i][c]){
		if(i>=j) continue;
		ob.add_edge(mp[pii(i,j)],t,1);
	}
	REP(i,n)for(int j=i;j<n;++j){
		int u=mp[pii(i,j)];
		REP(c,26)for(auto ni:g[i][c])for(auto nj:g[j][c]){
			int cni=ni, cnj=nj;
			if(cni>cnj) swap(cni,cnj);
			int v=mp[pii(cni,cnj)];
			ob.add_edge(u,v,2);
		}
	}
	
	ob.dijkstra(s);
	
	llong ans=ob.dist(t);
	cout<<(ans==ob.get_inf()?-1:ans)<<endl;
}