#include <cassert>
#include <iostream>
#include <limits>
#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 Hrana {
  int kam;
  int dt;
};

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<Hrana>> 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, 1});
      }
      // 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;
          hrany[odkial].push_back({kam, c.dt});
        }
      }
    }
  }

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

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

  Graf g(vstup);

  struct Trasa {
    int vrchol;
    long long t;

    // cim vacsi cas, tym mensia priorita
    bool operator<(const Trasa& x) const { return t > x.t; }

    Trasa potom(const Hrana& h) const { return {h.kam, t + h.dt}; }
  };

  vector<long long> minCasPrichodu;
  minCasPrichodu.resize(g.hrany.size(), numeric_limits<long long>::max());

  priority_queue<Trasa> pq;
  pq.push({0, 0});
  minCasPrichodu[0] = 0;
  while (!pq.empty()) {
    const Trasa trasa = pq.top();
    pq.pop();

    if (trasa.t != minCasPrichodu[trasa.vrchol]) {
      continue;
    }
    minCasPrichodu[trasa.vrchol] = trasa.t;

    if (g.jeCielovyVrchol(trasa.vrchol)) {
      cout << trasa.t << "\n";
      return 0;
    }

    for (const auto& h : g.hrany[trasa.vrchol]) {
      const Trasa kandidat = trasa.potom(h);
      if (minCasPrichodu[kandidat.vrchol] <= kandidat.t) {
        continue;
      }
      minCasPrichodu[kandidat.vrchol] = kandidat.t;
      pq.push(kandidat);
    }
  }

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