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

struct Cesta {
  int a, b;
  int dt;

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

    int z, c;
    string start;
    int startFaza;
    cin >> z >> c >> start >> startFaza;
    assert(c == 0 &&
           "Dijkstra vie riesit len pripady kde semafor vzdy svieti na zelenu");
  }
};

int main() {
  int n, m;
  cin >> n >> m;
  vector<vector<Cesta>> cesty;
  cesty.resize(n);
  for (int mi = 0; mi < m; mi++) {
    Cesta c;
    c.nacitaj();
    cesty[c.a].push_back(c);
  }

  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 Cesta& c) const { return {c.b, t + c.dt}; }
  };

  vector<long long> minCasPrichodu;
  minCasPrichodu.resize(n, 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 (trasa.vrchol == n - 1) {
      break;
    }

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

  long long vysl = minCasPrichodu[n - 1];
  cout << (vysl == numeric_limits<long long>::max() ? -1 : vysl) << "\n";
  return 0;
}