#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
#include <bits/stdc++.h>
#define REP(i, n) for (int i = 0; (i) < (int)(n); ++(i))
#define REP3(i, m, n) for (int i = (m); (i) < (int)(n); ++(i))
#define REP_R(i, n) for (int i = (int)(n)-1; (i) >= 0; --(i))
#define REP3R(i, m, n) for (int i = (int)(n)-1; (i) >= (int)(m); --(i))
#define ALL(x) ::std::begin(x), ::std::end(x)
using namespace std;

template <typename T>
void print_vector(T& vec) {
    stringstream ss;
    ss << "{";
    for (auto v : vec) ss << v << " ";
    ss << "}" << endl;
    cout << ss.str() << endl;
}

template <typename T>
void print_pairs(T& vec) {
    stringstream ss;
    ss << "{";
    for (auto v : vec) ss << v.first << "," << v.second << " ";
    ss << "}" << endl;
    cout << ss.str() << endl;
}

template <typename T>
string string_vector(vector<T>& vec) {
    stringstream ss;
    ss << "{";
    for (auto v : vec) ss << v << " ";
    ss << "}\n";
    return ss.str();
}

template <typename T>
string string_vector(vector<vector<T>>& vec) {
    stringstream ss;
    ss << "{";
    for (auto v : vec) {
        ss << "{";
        for (auto vv : v) ss << vv << " ";
        ss << "}";
    }
    ss << "}\n";
    return ss.str();
}

using ll = long long;
class Solution {
   public:
    vector<int> dp;
    vector<int> dp2;
    vector<int> bad;
    
    bool is_good(int s, int N, int M, const vector<int>& A, const vector<int>& B) {
        for(int i = 0; i < N; ++i) {
            if(!(s & (1<<i))) continue;
            if(s & bad[i]) return false;
        }        
        return true;
    }
    
    ll fix(int s, int N, int M, const vector<int>& A, const vector<int>& B) {
        if(s == 0) return 0;
        if(dp[s]) return dp[s]-1;

        //if(!is_good(s, N, M, A, B)) return N;
        
        ll min_cc = N;
        int b = 0;
        do {
            //res = fix(s & ~b, N, M, A, B);
            //if(b!=0 and is_good(s,N,M,A,B)) min_cc = min(min_cc, 1 + fix(s & ~b, N, M, A, B));
            bool good = false;
            if(!dp2[b]) dp2[b] = is_good(b, N, M, A, B) + 1;
            if(b!= 0 and dp2[b] - 1) {
                 min_cc = min(min_cc, 1 + fix(s & ~b, N, M, A, B));
            }
            
        } while((b = (b - s) & s));
        dp[s] = min_cc + 1;
        return min_cc;
    }

    ll solve(int N, int M, const vector<int>& A, const vector<int>& B) {
        dp.resize(1<<N);
        dp2.resize(1<<N);
        bad.resize(N, (1<<N) - 1);
        for(int i = 0; i < M; ++i) {            
            bad[A[i]] ^= (1<<B[i]);
            bad[B[i]] ^= (1<<A[i]);            
        }

        for(int i = 0; i < N; ++i) {
            bad[i] = bad[i] & ( ((1<<N) - 1) - ((1<<i)));
        }
        
        int min_cc = fix((1<<N) - 1, N, M, A, B);        
        return min_cc;
    }
};

// generated by online-judge-template-generator v4.7.1 (https://github.com/online-judge-tools/template-generator)
int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    Solution sol;
    int N, M;
    cin >> N >> M;
    vector<int> A(M), B(M);
    REP (i, M) { cin >> A[i] >> B[i];
        A[i]--, B[i]--;}
    auto ans = sol.solve(N, M, A, B);
    cout << ans << endl;
    return 0;
}
