#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;

using ll = long long;
using vi = vector<int>;
using vvi = vector<vi>;
using vl = vector<ll>;
using vvl = vector<vl>;
using vb = vector<bool>;
using vvb = vector<vb>;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
#define rep(i, s, n) for(int i = (int)(s); i < (int)(n); ++i)

ll INF = 1ll << 30;
struct edge{int x, y;};
vector<edge> G[1010][1010];
int dist[1010][1010];

int main(){
  int n, m;
  cin >> n >> m;
  vi A(m), B(m), C(m);
  rep(i, 0, m){
      char c;
      cin >> A[i] >> B[i] >> c;
      A[i]--; B[i]--;
      C[i] = c - 'a';
  }
  rep(i ,0, 1010){
      rep(j, 0, 1010){
          dist[i][j] = INF;
      }
  }
  rep(i, 0, m){
      rep(j, 0, m){
          if(C[i] == C[j]){
              G[A[i]][A[j]].push_back({B[i], B[j]});
              G[B[i]][B[j]].push_back({A[i], A[j]});
              G[A[i]][B[j]].push_back({B[i], A[j]});
              G[B[i]][A[j]].push_back({A[i], B[j]});
          }
      }
  }

  queue<pii> que;
  que.push({0, n-1});
  dist[0][n-1] = 0;
  
  while(!que.empty()){
      pii p = que.front();
      que.pop();
      int vx, vy;
      vx = p.first;
      vy = p.second;

      rep(i, 0, G[vx][vy].size()){
          int x, y;
          x = G[vx][vy][i].x;
          y = G[vx][vy][i].y;
          if(dist[x][y] > dist[vx][vy]+1){
              dist[x][y] = dist[vx][vy]+1;
              que.push({x, y});
          }
      }
  }

  int ans = INF;
  rep(i, 0, n){
      if(dist[i][i] != INF){
          ans = min(ans, dist[i][i]*2);
      }
  }
  rep(i, 0, n){
      rep(j, 0, n){
          if(dist[i][j] != INF && dist[j][i] - dist[i][j] == 1){
              ans = min(ans, dist[i][j]+dist[j][i]);
          }
      }
  }

  if(ans == INF){
      cout << -1 << endl;
  }
  else{
      cout << ans << endl;
  }

  return 0;
  
}
#include <bits/stdc++.h>
#define REP(i, N) for (int i = 0; i < (int)N; i++)
#define FOR(i, a, b) for (int i = a; i < (int)b; i++)

using namespace std;

int main() {
  int N;
  cin >> N;
  vector<int> used(2 * N);
  auto out = []() {
    cout << "No" << endl;
    exit(0);
  };
  REP(i, N) {
    int A, B;
    cin >> A >> B;
    if (A != -1 && B != -1 && A >= B) out();
    if (A != -1) {
      if (used[A - 1] != 0) out();
      used[A - 1] = i + 1;
    }
    if (B != -1) {
      if (used[B - 1] != 0) out();
      used[B - 1] = -(i + 1);
    }
  }
  vector<bool> dp(N + 1);
  dp[0] = 1;
  FOR(i, 1, N + 1) {
    REP(j, i)
    if (dp[j]) {
      bool ng = 0;
      REP(k, i - j) {
        int a = used[2 * j + k], b = used[2 * j + k + i - j];
        ng |= (a < 0) || (b > 0) || (a > 0 && b < 0 && b != -a);
      }
      if (!ng) dp[i] = 1;
    }
  }
  cout << (dp[N] ? "Yes" : "No") << endl;
  return 0;
}