Arkady likes to walk around his kitchen. His labyrinthine kitchen consists of several important places connected with passages. Unfortunately it happens that these passages are flooded with milk so that it's impossible to pass through them. Namely, it's possible to pass through each passage in any direction only during some time interval.

The lengths of all passages are equal and Arkady makes through them in one second. For security reasons, Arkady can never stop, also, he can't change direction while going through a passage. In other words, if he starts walking in some passage, he should reach its end and immediately leave the end.

Today Arkady needs to quickly reach important place n from place 1. He plans to exit the place 1 at time moment 0 and reach the place n as early as he can. Please find the minimum time he should spend on his way.

Input

The first line contains two integers n and m (1 ≤ n ≤ 5·105, 0 ≤ m ≤ 5·105) — the number of important places and the number of passages, respectively.

After that, m lines follow, each of them describe one passage. Each line contains four integers a, b, l and r (1 ≤ a, b ≤ n, a ≠ b, 0 ≤ l < r ≤ 109) — the places the passage connects and the time segment during which it's possible to use this passage.

Output

Print one integer — minimum time Arkady should spend to reach the destination. If he can't reach the place n, print -1.

Examples

Input

5 6
1 2 0 1
2 5 2 3
2 5 0 1
1 3 0 1
3 4 1 2
4 5 2 3


Output

3


Input

2 1
1 2 1 100


Output

-1

Note

In the first example Arkady should go through important places 1 → 3 → 4 → 5.

In the second example Arkady can't start his walk because at time moment 0 it's impossible to use the only passage.
#include <bits/stdc++.h>
using namespace std;
const double pi = acos(0.0) * 2.0;
const long double eps = 1e-10;
const int step[8][2] = {{-1, 0}, {0, 1}, {1, 0},  {0, -1},
                        {-1, 1}, {1, 1}, {1, -1}, {-1, -1}};
template <class T>
inline T abs1(T a) {
  return a < 0 ? -a : a;
}
template <typename t, typename t1>
t min1(t a, t1 b) {
  return a < b ? a : b;
}
template <typename t, typename... arg>
t min1(t a, arg... arr) {
  return min1(a, min1(arr...));
}
template <typename t, typename t1>
t max1(t a, t1 b) {
  return a > b ? a : b;
}
template <typename t, typename... arg>
t max1(t a, arg... arr) {
  return max1(a, max1(arr...));
}
inline int jud(double a, double b) {
  if (abs(a) < eps && abs(b) < eps)
    return 0;
  else if (abs1(a - b) / max(abs1(a), abs1(b)) < eps)
    return 0;
  if (a < b) return -1;
  return 1;
}
template <typename t>
inline int jud(t a, t b) {
  if (a < b) return -1;
  if (a == b) return 0;
  return 1;
}
template <typename it, typename t1>
inline int find(t1 val, it a, int na, bool f_small = 1, bool f_lb = 1) {
  if (na == 0) return 0;
  int be = 0, en = na - 1;
  if (*a <= *(a + na - 1)) {
    if (f_lb == 0)
      while (be < en) {
        int mid = (be + en + 1) / 2;
        if (jud(*(a + mid), val) != 1)
          be = mid;
        else
          en = mid - 1;
      }
    else
      while (be < en) {
        int mid = (be + en) / 2;
        if (jud(*(a + mid), val) != -1)
          en = mid;
        else
          be = mid + 1;
      }
    if (f_small && jud(*(a + be), val) == 1) be--;
    if (!f_small && jud(*(a + be), val) == -1) be++;
  } else {
    if (f_lb)
      while (be < en) {
        int mid = (be + en + 1) / 2;
        if (jud(*(a + mid), val) != -1)
          be = mid;
        else
          en = mid - 1;
      }
    else
      while (be < en) {
        int mid = (be + en) / 2;
        if (jud(*(a + mid), val) != 1)
          en = mid;
        else
          be = mid + 1;
      }
    if (!f_small && jud(*(a + be), val) == -1) be--;
    if (f_small && jud(*(a + be), val) == 1) be++;
  }
  return be;
}
template <class T>
inline T lowb(T num) {
  return num & (-num);
}
inline int bitnum(unsigned int nValue) { return __builtin_popcount(nValue); }
inline int bitnum(int nValue) { return __builtin_popcount(nValue); }
inline int bitnum(unsigned long long nValue) {
  return __builtin_popcount(nValue) + __builtin_popcount(nValue >> 32);
}
inline int bitnum(long long nValue) {
  return __builtin_popcount(nValue) + __builtin_popcount(nValue >> 32);
}
inline int bitmaxl(unsigned int a) {
  if (a == 0) return 0;
  return 32 - __builtin_clz(a);
}
inline int bitmaxl(int a) {
  if (a == 0) return 0;
  return 32 - __builtin_clz(a);
}
inline int bitmaxl(unsigned long long a) {
  int temp = a >> 32;
  if (temp) return 32 - __builtin_clz(temp) + 32;
  return bitmaxl(int(a));
}
inline int bitmaxl(long long a) {
  int temp = a >> 32;
  if (temp) return 32 - __builtin_clz(temp) + 32;
  return bitmaxl(int(a));
}
long long pow(long long n, long long m, long long mod = 0) {
  if (m < 0) return 0;
  long long ans = 1;
  long long k = n;
  while (m) {
    if (m & 1) {
      ans *= k;
      if (mod) ans %= mod;
    }
    k *= k;
    if (mod) k %= mod;
    m >>= 1;
  }
  return ans;
}
template <class t1, class t2>
inline void add(t1 &a, t2 b, int mod = -1) {
  if (mod == -1) mod = 1000000007;
  a += b;
  while (a >= mod) a -= mod;
  while (a < 0) a += mod;
}
template <class t>
void output1(t arr) {
  for (int i = 0; i < (int)arr.size(); i++) cerr << arr[i] << ' ';
  cerr << endl;
}
template <class t>
void output2(t arr) {
  for (int i = 0; i < (int)arr.size(); i++) output1(arr[i]);
}
const int maxn = 505000;
bool flag = 0;
int dp[maxn], nxtdp[maxn][3], tnxt[maxn][3];
int n, m;
struct link {
  int nxt, bef;
  bool exist;
} e[maxn * 2];
int head[maxn];
struct edge {
  int be, en, a, b;
  bool operator<(const edge &re) const {
    if (be == re.be) {
      return en < re.en;
    }
    return be < re.be;
  }
} alle[maxn];
priority_queue<pair<int, pair<int, int> >, vector<pair<int, pair<int, int> > >,
               greater<pair<int, pair<int, int> > > >
    pq;
int findnxt(int no, int t, int cate) {
  for (int rit = head[no]; rit != -1; rit = e[rit].nxt) {
    int it = rit / 2;
    if (alle[it].be <= t) {
      t = max(alle[it].en - (alle[it].en % 2 != 2 - cate) * (cate != 3), t);
    } else
      break;
  }
  return t;
}
void addedge(int no, int i) {
  e[i].bef = -1;
  e[i].exist = 1;
  e[i].nxt = head[no];
  if (head[no] != -1) {
    e[head[no]].bef = i;
  }
  head[no] = i;
  e[i].exist = 1;
}
void deledge(int i) {
  if (e[i].bef != -1) {
    e[e[i].bef].nxt = e[i].nxt;
  }
  if (e[i].nxt != -1) {
    e[e[i].nxt].bef = e[i].bef;
  }
  e[i].exist = 0;
}
int getrcate(int cate) {
  if (cate == 3)
    return 3;
  else if (cate == 2)
    return 1;
  else if (cate == 1)
    return 2;
  else
    return 0;
}
void updrcate(int rcate, int nxtno, int t, int add) {
  if (((rcate | dp[nxtno]) ^ dp[nxtno]) >= 3) {
    cout << dp[nxtno] << ' ' << rcate << endl;
    exit(0);
  }
  if ((dp[nxtno] | rcate) > (dp[nxtno] | nxtdp[nxtno][add])) {
    if (((rcate | dp[nxtno]) ^ dp[nxtno]) != t % 2 + 1) {
      cout << dp[nxtno] << ' ' << rcate << ' ' << t;
      exit(0);
    }
    pq.push(make_pair(t, make_pair(4 + rcate, nxtno)));
    nxtdp[nxtno][add] = rcate;
    pq.push(make_pair(t + 1, make_pair(0, nxtno)));
  }
}
void add(int no1, int eno, int no, int t) {
  int more = getrcate(dp[no1]) | dp[no];
  more ^= dp[no];
  if ((more & (t % 2 + 1)) && alle[eno].en > t)
    updrcate(more & (t % 2 + 1), no, t, 2 - t % 2);
  if ((more & (2 - t % 2)) && alle[eno].en > t + 1 &&
      tnxt[no1][more & (2 - t % 2)] > t)
    updrcate(more & (2 - t % 2), no, t + 1, t % 2 + 1);
}
int main() {
  ios_base::sync_with_stdio(0);
  scanf("%d%d", &n, &m);
  if (n == 1) {
    cout << 0 << endl;
    return 0;
  }
  for (int i = 0; i < m; i++) {
    int a, b, l, r;
    scanf("%d%d%d%d", &a, &b, &l, &r);
    a--;
    b--;
    alle[i].a = a;
    alle[i].b = b;
    alle[i].be = l;
    alle[i].en = r;
  }
  auto ju = [&]() { return n == 100000 && m == 149999; };
  flag = ju();
  sort(alle, alle + m);
  memset(head, -1, sizeof(head));
  for (int i = m - 1; i >= 0; i--) {
    addedge(alle[i].a, i * 2);
    addedge(alle[i].b, i * 2 + 1);
  }
  dp[0] = 2;
  pq.push(make_pair(findnxt(0, 0, 2), make_pair(3, 0)));
  tnxt[0][2] = findnxt(0, 0, 2);
  for (int i = 0; i < m; i++) {
    pq.push(make_pair(alle[i].be, make_pair(-1, i)));
    pq.push(make_pair(alle[i].en, make_pair(1, i)));
  }
  if (pq.size() && pq.top().first != 0) {
    puts("-1");
    return 0;
  }
  for (; pq.size();) {
    int t = pq.top().first, cate = pq.top().second.first,
        no = pq.top().second.second;
    pq.pop();
    if (no == n - 1 && cate < 2 && cate != -1 && cate != 1) {
      printf("%d\n", t);
      return 0;
    }
    if (cate > 4) {
      dp[no] |= nxtdp[no][2 - t % 2];
      nxtdp[no][2 - t % 2] = 0;
    } else if (cate > 1) {
      if (!(dp[no] & (cate - 1))) {
        cout << t << ' ' << no << ' ' << dp[no] << ' ' << cate - 1 << endl;
        tnxt[no][cate - 1];
        exit(0);
      }
      dp[no] &= 3 ^ (cate - 1);
    } else if (cate == 1) {
      deledge(no * 2);
      deledge(no * 2 + 1);
    } else if (cate == 0) {
      if (dp[no] != 3 && 2 - dp[no] != t % 2) {
        pq.push(make_pair(t + 1, make_pair(0, no)));
        continue;
      }
      assert(dp[no] & (2 - (t % 2)));
      int rt = findnxt(no, t, (2 - (t % 2)));
      tnxt[no][2 - t % 2] = rt;
      pq.push(make_pair(rt, make_pair(1 + (2 - t % 2), no)));
      for (int rit = head[no]; rit != -1; rit = e[rit].nxt) {
        int it = rit / 2;
        if (alle[it].be <= t) {
          int nxtno = alle[it].a + alle[it].b - no;
          add(no, it, nxtno, t);
        } else
          break;
      }
    } else {
      int a = alle[no].a, b = alle[no].b;
      if (dp[a] < dp[b]) swap(a, b);
      if ((dp[a] == 2 && dp[b] == 1) || (dp[a] == 1 && dp[b] == 2) ||
          (dp[a] == 3 && dp[b] == 3) || (dp[a] == 0 && dp[b] == 0)) {
        continue;
      }
      if ((t % 2 + 1 == dp[a] || dp[a] == 0) &&
          (t % 2 + 1 == dp[b] || dp[b] == 0)) {
        if (alle[no].en > t) pq.push(make_pair(t + 1, make_pair(-1, no)));
        continue;
      }
      add(a, no, b, t);
      add(b, no, a, t);
    }
  }
  printf("-1\n");
  return 0;
}
