#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC push_options
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx")
#include <algorithm>
#include <cmath>
#include <functional>
#include <iomanip>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <vector>
using namespace std;
using ll = long long;
#define rep(i, j, n) for (int i = j; i < (n); ++i)
#define rrep(i, j, n) for (int i = (n)-1; j <= i; --i)
#define vi vector<ll>
#define vii vector<vector<ll>>
template <typename T>
std::ostream& operator<<(std::ostream& os, std::vector<T>& a) {
  for (size_t i = 0; i < a.size(); ++i) os << (i > 0 ? " " : "") << a[i];
  return os << '\n';
}
template <typename T>
std::ostream& operator<<(std::ostream& os, pair<T, T>& p) {
  return os << "{ " << p.first << ", " << p.second << " }" << std::endl;
}
template <typename T>
std::istream& operator>>(std::istream& is, pair<T, T>& p) {
  return is >> p.first >> p.second;
}
template <typename T>
std::istream& operator>>(std::istream& is, std::vector<T>& a) {
  for (T& x : a) is >> x;
  return is;
}
void chmin(int& a, int b) {
  if (a > b) a = b;
}

[[maybe_unused]] constexpr ll MOD = 1e9 + 7;
[[maybe_unused]] constexpr int INF = 0x3f3f3f3f;
[[maybe_unused]] constexpr ll INFL = 0x3f3f3f3f3f3f3f3fLL;

bool dfs(int v, int c, vector<int>& col, vector<vector<int>>& g) {
  col[v] = c;
  for (int nv : g[v]) {
    if (col[nv] == c) return false;
    if (col[nv] == 0 && !dfs(nv, -c, col, g)) return false;
  }
  return true;
}

int main() {
  cin.tie(0)->sync_with_stdio(0);
  int n, m;
  cin >> n >> m;
  // 赤で塗る頂点を固定、のれらの頂点を除外してできたグラフで、全ての連結成分を二色で塗れるか
  //
  vector<pair<int, int>> es;
  rep(i, 0, m) {
    int a, b;
    cin >> a >> b;
    --a, --b;
    es.emplace_back(a, b);
  }

  ll ans = 0;
  rep(bit, 0, 1 << n) {
    // 赤で塗る頂点
    // 二部グラフ判定
    bool bad = false;
    vector<vector<int>> g(n);
    vector<int> col(n);
    for (auto& [a, b] : es) {
      if ((bit >> a & 1) && (bit >> b & 1)) {
        bad = true;
        break;
      }
      if ((bit >> a & 1) == 0 && (bit >> b & 1) == 0) {
        g[a].push_back(b);
        g[b].push_back(a);
      }
    }
    if (bad) continue;
    ll tmp = 1;
    rep(i, 0, n) {
      if (bit >> i & 1) continue;
      if (col[i] == 0) {
        if (!dfs(i, 1, col, g)) {
          tmp *= 0;
          break;
        } else
          tmp *= 2;
      }
    }
    ans += tmp;
  }
  cout << ans;
  return 0;
}

#include<iostream>
#include<string>
#include<algorithm>
#include<cmath>
#include<vector>
#include<stack>
#include<queue>
#include<map>
#include<set>
#include<iomanip>
#include<tuple>
#include<cstring>
#include<bitset>

#define REP(i,n) for(int i=0;i<(int)n;i++)
#define ALL(x) (x).begin(),(x).end()
#define SZ(x) ((int)(x).size())
#define pb push_back
#define eb emplace_back

#define INF 1000000000
#define INFLL 1000000000000000000LL

using namespace std;

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; }

using ll = long long;
using P = pair<int, int>;
using PLL = pair<ll, ll>;

#define MAX_N 1000+100

int N, M, d[MAX_N][MAX_N], ans;

vector<int> G[MAX_N][26];
queue<P> que;
bool visit[MAX_N][MAX_N];

int main() {

	cin >> N >> M;

	REP(i, M) {
		int A, B;
		char C;

		cin >> A >> B >> C;
		A--;
		B--;
		G[A][C-'a'].pb(B);
		G[B][C-'a'].pb(A);
	}

	ans = INF;

	REP(i, N)REP(j, N)d[i][j] = INF;

	que.push({ 0,N - 1 });
	d[0][N - 1] = 0;
	visit[0][N - 1] = true;

	while (!que.empty()) {
		int u = que.front().first;
		int v = que.front().second;
		que.pop();

		REP(i, 26) {
			for (auto&& e_u : G[u][i]) {
				for (auto&& e_v : G[v][i]) {
					if (visit[e_u][e_v])continue;
					visit[e_u][e_v] = true;
					que.push({ e_u,e_v });
					d[e_u][e_v] = d[u][v] + 2;
				}
			}
		}
	}

	REP(i, N) {
		chmin(ans, d[i][i]);
	}

	REP(i, N) {
		REP(j, 26) {
			for (auto&& x : G[i][j]) {
				chmin(ans, d[i][x] + 1);
			}
		}
	}

	cout << (ans >= INF ? -1 : ans) << endl;

	return 0;
}