#include <bits/stdc++.h>   using namespace std;   const int maxn = 5e5 + 20;   struct edge {     int v, l, r;     edge() {}     edge(int a, int b, int c) {       v = a;       l = b;       r = c;     }   };   struct nd {     int no, lim, to;     nd() {}     nd(int a, int b, int c) {       no = a;       lim = b;       to = c;     }   };   bool operator<(const nd& a, const nd& b) {     if (a.no != b.no) {       return a.no > b.no;     }     if (a.lim != b.lim) {       return a.lim > b.lim;     }     return a.to < b.to;   }   bool operator<(const edge& a, const edge& b) {     if (a.l != b.l) {       return a.l < b.l;     }     return a.r < b.r;   }   vector<edge> G[2 * maxn];   int now[2 * maxn];   int main() {     int n, m, u, v, l, r;     scanf( %d%d , &n, &m);     for (int i = 0; i < m; i++) {       scanf( %d%d%d%d , &u, &v, &l, &r);       if (l & 1) {         if (r & 1) {           G[u].push_back(edge(v + n, l + 1, r - 1));           G[v].push_back(edge(u + n, l + 1, r - 1));           G[u + n].push_back(edge(v, l, r - 2));           G[v + n].push_back(edge(u, l, r - 2));         } else {           if (l + 1 < r) {             G[u].push_back(edge(v + n, l + 1, r - 2));             G[v].push_back(edge(u + n, l + 1, r - 2));           }           G[u + n].push_back(edge(v, l, r - 1));           G[v + n].push_back(edge(u, l, r - 1));         }       } else {         if (r & 1) {           G[u].push_back(edge(v + n, l, r - 1));           G[v].push_back(edge(u + n, l, r - 1));           if (l + 1 < r) {             G[u + n].push_back(edge(v, l + 1, r - 2));             G[v + n].push_back(edge(u, l + 1, r - 2));           }         } else {           G[u].push_back(edge(v + n, l, r - 2));           G[v].push_back(edge(u + n, l, r - 2));           G[u + n].push_back(edge(v, l + 1, r - 1));           G[v + n].push_back(edge(u, l + 1, r - 1));         }       }     }     for (int i = 1; i <= n + n; i++) {       sort(G[i].begin(), G[i].end());     }     priority_queue<nd> Q;     Q.push(nd(0, 0, 1));     int ans = 0x3f3f3f3f;     nd t;     while (!Q.empty()) {       t = Q.top();       int u = t.to, no = t.no, lim = t.lim;       Q.pop();       if (u == n || u == n * 2) {         ans = min(ans, no);       }       for (int& i = now[u]; i < G[u].size(); i++) {         if (lim < G[u][i].l) {           break;         }         if (no <= G[u][i].r) {           Q.push(nd(max(no + 1, G[u][i].l + 1), G[u][i].r + 1, G[u][i].v));         }       }     }     if (ans == 0x3f3f3f3f) {       printf( -1 n );     } else {       printf( %d n , ans);     }     return 0;   }   