#include <cstdio>
#include <queue>

const int MAXN = 5e4 + 10;
const int MAXM = 1e5 + 10;

struct EDGE {
  int v, next, a, b;
} edge[MAXM << 1];

int edgeNum, head[MAXN];
void AddEdge(int u, int v, int a, int b) {
  edge[++edgeNum] = {v, head[u], a, b};
  head[u] = edgeNum;
}

int n, m;

struct Dis {
  int a = 0x3f3f3f3f, b = 0x3f3f3f3f;
} dis[MAXN];
int vis[MAXN], in_que[MAXN];
std::queue<int> queue;

bool Relax(int u, int v, int a, int b) {
  if (std::max(dis[u].a, a) + std::max(dis[u].b, b) < dis[v].a + dis[v].b) {
    dis[v].a = std::max(dis[u].a, a), dis[v].b = std::max(dis[u].b, b);
    return true;
  }
  return false;
}

void SPFA() {
  dis[1] = {0, 0};
  queue.push(1);
  while (!queue.empty()) {
    int u = queue.front();
    queue.pop();
    if (++vis[u] == n + 1) return ;

    for (int i = head[u]; i; i = edge[i].next) {
      int v = edge[i].v, a = edge[i].a, b = edge[i].b;
      if (Relax(u, v, a, b) && !in_que[v]) {
        queue.push(v);
        in_que[v] = 1;
      }
    }
  }
}

int main() {
  #ifdef LOCAL
    freopen("!input.in", "r", stdin);
    freopen("!output.out", "w", stdout);
  #else
    freopen("magicalforest.in", "r", stdin);
    freopen("magicalforest.out", "w", stdout);
  #endif

  scanf("%d %d", &n, &m);
  for (int i = 1, u, v, a, b; i <= m; ++i) {
    scanf("%d %d %d %d", &u, &v, &a, &b);
    AddEdge(u, v, a, b);
    AddEdge(v, u, a, b);
  }

  SPFA();

  if (dis[n].a == 0x3f3f3f3f || dis[n].b == 0x3f3f3f3f) {
    printf("-1");
  } else {
    printf("%d\n", dis[n].a + dis[n].b);
  }
  return 0;
}