#include <cassert>
#include <iostream>
#include <queue>
#include <vector>
using namespace std;

struct Semafor {
  int z, c;
  string s;
  int f;

  void nacitaj() {
    cin >> z >> c >> s >> f;
    assert(z == 1 && c == 1 && f == 1);
  }
};

struct Cesta {
  int a, b;
  int dt;
  Semafor semafor;

  void nacitaj() {
    cin >> a >> b >> dt;
    assert(dt <= 10);
    a--;
    b--;
    semafor.nacitaj();
  }
};

struct Graf {
  int n;  // pocet realnych vrcholov

  // 0..n-1 sú pre párne časy, n..2n-1 sú pre nepárne
  // časy. Mozu tam byt dalsie polozky pre pomocne hrany
  // (na reprezentaciu hran s dlzkou > 1)
  vector<vector<int>> hrany;

  Graf(int n0) : n(n0) {
    hrany.resize(2 * n0);

    // treba pridať hrany, ktoré zodpovedajú čakaniu
    for (int i = 0; i < n; i++) {
      hrany[i].push_back(n + i);
      hrany[n + i].push_back(i);
    }
  }

  void pridajHrany(const Cesta& c) {
    int odkial, kam;
    if (c.semafor.s == "Z") {
      odkial = c.a;
      kam = c.b + (c.dt % 2) * n;
    } else if (c.semafor.s == "C") {
      odkial = c.a + n;
      kam = c.b + ((c.dt + 1) % 2) * n;
    } else {
      assert(false && "Neznamy zaciatocny stav");
    }

    int aktualnyVrchol = odkial;
    for (int i = 1; i < c.dt; i++) {
      int pomocnyVrchol = hrany.size();
      hrany.push_back({});
      hrany[aktualnyVrchol].push_back(pomocnyVrchol);
      aktualnyVrchol = pomocnyVrchol;
    }
    hrany[aktualnyVrchol].push_back(kam);
  }

  bool jeCielovyVrchol(int v) const { return (v < 2 * n) && (v % n == n - 1); }
};

int main() {
  int n, m;
  cin >> n >> m;

  Graf g(n);
  for (int mi = 0; mi < m; mi++) {
    Cesta c;
    c.nacitaj();
    g.pridajHrany(c);
  }

  vector<int> minCasPrichodu;
  minCasPrichodu.resize(g.hrany.size(), -1);

  queue<int> Q;
  Q.push(0);
  minCasPrichodu[0] = 0;
  while (!Q.empty()) {
    int aktualnyVrchol = Q.front();
    Q.pop();

    int t = minCasPrichodu[aktualnyVrchol];
    for (int sused : g.hrany[aktualnyVrchol]) {
      if (minCasPrichodu[sused] != -1) {
        continue;
      }
      if (g.jeCielovyVrchol(sused)) {
        cout << t + 1 << "\n";
        return 0;
      }
      minCasPrichodu[sused] = t + 1;
      Q.push(sused);
    }
  }

  cout << "-1\n";
  return 0;
}