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

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

  int perioda() const { return z + c; }

  bool jeZelenaVCase(int t) const {
    if (s == "Z") {
      if (t < f) {
        return true;
      }
      t -= f;
      t %= perioda();
      return t >= c;
    } else {
      assert(s == "C");
      if (t < f) {
        return false;
      }
      t -= f;
      t %= perioda();
      return t < z;
    }
  }

  void nacitaj() { cin >> z >> c >> s >> f; }
};

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

  void nacitaj() {
    cin >> a >> b >> dt;
    a--;
    b--;
    semafor.nacitaj();
  }
};

int gcd(int a, int b) {
  if (a == 0) {
    return b;
  }
  if (b == 0) {
    return a;
  }
  if (a == b) {
    return a;
  }
  return gcd(a % b, b % a);
}

int nsn(int a, int b) { return a * (b / gcd(a, b)); }

struct Vstup {
  int n, m;
  vector<Cesta> cesty;

  void nacitaj() {
    cin >> n >> m;
    cesty.resize(m);
    for (auto& c : cesty) {
      c.nacitaj();
    }
  }

  int perioda() const {
    int vysl = 1;
    for (const auto& c : cesty) {
      vysl = nsn(vysl, c.semafor.perioda());
    }
    return vysl;
  }
};

struct Graf {
  int n;  // pocet realnych vrcholov
  int perioda;

  // kn..(k+1)n-1 sú pre časy t také, že t % perioda == k
  vector<vector<int>> hrany;

  Graf(const Vstup& vstup) {
    n = vstup.n;
    perioda = vstup.perioda();
    assert((long long)n * perioda <= 1023456789);
    hrany.resize(n * perioda);
    for (int k = 0; k < perioda; k++) {
      // hrany zodpovedajuce cakaniu
      for (int vi = 0; vi < n; vi++) {
        int a = k * n + vi;
        int b = ((k + 1) % perioda) * n + vi;
        hrany[a].push_back(b);
      }
      // hrany zodpovedajuce cestam
      for (const auto& c : vstup.cesty) {
        if (c.semafor.jeZelenaVCase(k)) {
          int odkial = k * n + c.a;
          int kam = ((k + c.dt) % perioda) * n + c.b;

          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 < perioda * n) && (v % n == n - 1);
  }
};

int main() {
  Vstup vstup;
  vstup.nacitaj();

  Graf g(vstup);

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