#include <bits/stdc++.h>

#define int int64_t

const int kMaxN = 205, kMaxM = 5e4 + 5;

int n, m;
int u[kMaxM], v[kMaxM], c[kMaxM], d[kMaxM];
int dis1[kMaxN], dis2[kMaxN], dis3[kMaxN], dis4[kMaxN];
bool ont1[kMaxM], ont2[kMaxM], ont3[kMaxM], ont4[kMaxM];
std::vector<std::pair<int, int>> G1[kMaxN], G2[kMaxN];

void dijkstra1(int s, int *dis, bool *ont) {
  static int pre[kMaxN];
  static bool vis[kMaxN];
  for (int i = 1; i <= n; ++i) dis[i] = 1e18, pre[i] = vis[i] = 0;
  dis[s] = 0;
  for (int cs = 1; cs <= n; ++cs) {
    int u = 0;
    for (int i = 1; i <= n; ++i)
      if (!vis[i] && (!u || dis[i] < dis[u]))
        u = i;
    if (!u) break;
    vis[u] = 1;
    for (auto [v, id] : G1[u]) {
      if (dis[v] > dis[u] + c[id]) {
        dis[v] = dis[u] + c[id];
        ont[pre[v]] = 0, ont[pre[v] = id] = 1;
      }
    }
  }
}

void dijkstra2(int s, int *dis, bool *ont) {
  static int pre[kMaxN];
  static bool vis[kMaxN];
  for (int i = 1; i <= n; ++i) dis[i] = 1e18, pre[i] = vis[i] = 0;
  dis[s] = 0;
  for (int cs = 1; cs <= n; ++cs) {
    int u = 0;
    for (int i = 1; i <= n; ++i)
      if (!vis[i] && (!u || dis[i] < dis[u]))
        u = i;
    if (!u) break;
    vis[u] = 1;
    for (auto [v, id] : G2[u]) {
      if (dis[v] > dis[u] + c[id]) {
        dis[v] = dis[u] + c[id];
        ont[pre[v]] = 0, ont[pre[v] = id] = 1;
      }
    }
  }
}

int dijkstra3(int s, int x, int nid) {
  static int dis[kMaxN];
  static bool vis[kMaxN];
  for (int i = 1; i <= n; ++i) dis[i] = 1e18, vis[i] = 0;
  dis[s] = 0;
  for (int cs = 1; cs <= n; ++cs) {
    int u = 0;
    for (int i = 1; i <= n; ++i)
      if (!vis[i] && (!u || dis[i] < dis[u]))
        u = i;
    if (!u) break;
    vis[u] = 1;
    for (auto [v, id] : G1[u]) {
      if (id != nid && dis[v] > dis[u] + c[id]) {
        dis[v] = dis[u] + c[id];
      }
    }
  }
  return dis[x];
}

int dijkstra4(int s, int x, int nid) {
  static int dis[kMaxN];
  static bool vis[kMaxN];
  for (int i = 1; i <= n; ++i) dis[i] = 1e18, vis[i] = 0;
  dis[s] = 0;
  for (int cs = 1; cs <= n; ++cs) {
    int u = 0;
    for (int i = 1; i <= n; ++i)
      if (!vis[i] && (!u || dis[i] < dis[u]))
        u = i;
    if (!u) break;
    vis[u] = 1;
    for (auto [v, id] : G2[u]) {
      if (id != nid && dis[v] > dis[u] + c[id]) {
        dis[v] = dis[u] + c[id];
      }
    }
  }
  return dis[x];
}

int getdis1(int x, int id) { // 从 1 开始走正图，不走 id，到 x 的最短路
  if (!ont1[id]) return dis1[x];
  else return dijkstra3(1, x, id);
}

int getdis2(int x, int id) { // 从 n 开始走正图，不走 id，到 x 的最短路
  if (!ont2[id]) return dis2[x];
  else return dijkstra3(n, x, id);
}

int getdis3(int x, int id) {
  if (!ont3[id]) return dis3[x];
  else return dijkstra4(1, x, id);
}

int getdis4(int x, int id) {
  if (!ont4[id]) return dis4[x];
  else return dijkstra4(n, x, id);
}

void dickdreamer() {
  std::cin >> n >> m;
  for (int i = 1; i <= m; ++i) {
    std::cin >> u[i] >> v[i] >> c[i] >> d[i];
    G1[u[i]].emplace_back(v[i], i);
    G2[v[i]].emplace_back(u[i], i);
  }
  dijkstra1(1, dis1, ont1), dijkstra1(n, dis2, ont2);
  dijkstra2(1, dis3, ont3), dijkstra2(n, dis4, ont4);
  int ans = dis1[n] + dis2[1];
  for (int i = 1; i <= m; ++i) {
    int res1 = std::min(getdis1(n, i), getdis1(v[i], i) + getdis4(u[i], i) + c[i]);
    int res2 = std::min(getdis2(1, i), getdis2(v[i], i) + getdis3(u[i], i) + c[i]);
    // int res1 = getdis1(n, i);
    // int res2 = getdis2(1, i);
    // std::cerr << res1 << ' ' << res2 << ' ' << getdis2(3, i) << '\n';
    ans = std::min(ans, res1 + res2 + d[i]);
  }
  if (ans > 1e15) std::cout << "-1\n";
  else std::cout << ans << '\n';
}

int32_t main() {
#ifdef ORZXKR
  freopen("in.txt", "r", stdin);
  freopen("out.txt", "w", stdout);
#endif
  std::ios::sync_with_stdio(0), std::cin.tie(0), std::cout.tie(0);
  int T = 1;
  // std::cin >> T;
  while (T--) dickdreamer();
  // std::cerr << 1.0 * clock() / CLOCKS_PER_SEC << "s\n";
  return 0;
}