#include <bits/stdc++.h>

// #define int int64_t

const int kMaxN = 1e5 + 5, kMaxM = 2e5 + 5;

int n, m, cnt;
int u[kMaxM], v[kMaxM], c[kMaxM], w[kMaxM], idx[kMaxN];
std::unordered_map<int, int> id[kMaxN];
std::unordered_map<int, int64_t> val[kMaxN];
std::vector<std::tuple<int, int, int, int64_t>> G[kMaxM * 5][2][2]; // [to, o1, o2, w]

// int cost(int a, int o1, int b, int o2) {
//   if (o2) return w[b];
//   int u, ret;
//   if (::u[a] == ::u[b] || ::u[a] == ::v[b]) u = ::u[a];
//   else u = ::v[a];
//   if (o1 && c[a] == c[b]) return mp[u][c[b]] - w[a] - w[b];
//   else return mp[u][c[b]] - w[b];
// }

void dijkstra() {
  static int dis[kMaxM][2][2];
  std::priority_queue<std::tuple<int, int, int, int>> q;
  memset(dis, 0x3f, sizeof(dis));
  for (int i = 1; i <= m; ++i) {
    if (u[i] == 1) {
      dis[i][0][0] = val[1][c[i]] - w[i];
      dis[i][0][1] = w[i];
      q.emplace(-dis[i][0][0], i, 0, 0);
      q.emplace(-dis[i][0][1], i, 0, 1);
    } else if (v[i] == 1) {
      dis[i][1][0] = val[1][c[i]] - w[i];
      dis[i][1][1] = w[i];
      q.emplace(-dis[i][1][0], i, 0, 0);
      q.emplace(-dis[i][1][1], i, 0, 1);
    }
  }
  for (; !q.empty();) {
    auto [d, i, o1, o2] = q.top();
    q.pop();
    // std::cerr << d << ' ' << i << ' ' << o1 << ' ' << o2 << '\n';
    // for (int j = 1; j <= m; ++j) {
    //   if (i == j) continue;
    //   for (int o3 = 0; o3 < 2; ++o3) {
    //     for (int o4 = 0; o4 < 2; ++o4) {
    //       if ((o1 ? u[i] : v[i]) == (!o3 ? u[j] : v[j])) {
    //         int val = dis[i][o1][o2] + cost(i, o2, j, o4);
    //         if (dis[j][o3][o4] > val) {
    //           dis[j][o3][o4] = val;
    //           q.emplace(-dis[j][o3][o4], j, o3, o4);
    //         }
    //       }
    //     }
    //   }
    // }
  }
  int ret = 1e18;
  for (int i = 1; i <= m; ++i) {
    for (int o1 = 0; o1 < 2; ++o1) {
      for (int o2 = 0; o2 < 2; ++o2) {
        if ((o1 ? u[i] : v[i]) == n) ret = std::min(ret, dis[i][o1][o2]);
      }
    }
  }
  if (ret <= 1e15) std::cout << ret << '\n';
  else std::cout << "-1\n";
}

void spfa() {
  static __int128_t dis[kMaxM * 5][2][2];
  static bool inq[kMaxM * 5][2][2];
  for (int i = 1; i <= cnt; ++i)
    for (int o1 = 0; o1 < 2; ++o1)
      for (int o2 = 0; o2 < 2; ++o2)
        dis[i][o1][o2] = (__int128_t)1e18 * (__int128_t)1e18;
  std::queue<std::tuple<int, int, int>> q;
  for (int i = 1; i <= m; ++i) {
    if (u[i] == 1) {
      dis[i][0][0] = val[1][c[i]] - w[i];
      dis[i][0][1] = w[i];
      q.emplace(i, 0, 0);
      q.emplace(i, 0, 1);
      inq[i][0][0] = inq[i][0][1] = 1;
    } else if (v[i] == 1) {
      dis[i][1][0] = val[1][c[i]] - w[i];
      dis[i][1][1] = w[i];
      q.emplace(i, 1, 0);
      q.emplace(i, 1, 1);
      inq[i][1][0] = inq[i][1][1] = 1;
    }
  }
  for (; !q.empty();) {
    auto [u, o1, o2] = q.front(); q.pop();
    inq[u][o1][o2] = 0;
    // std::cerr << (int64_t)dis[u][o1][o2] << '\n';
    for (auto [v, o3, o4, w] : G[u][o1][o2]) {
      if (dis[v][o3][o4] > dis[u][o1][o2] + w) {
        dis[v][o3][o4] = dis[u][o1][o2] + w;
        if (!inq[v][o3][o4]) {
          q.emplace(v, o3, o4);
          inq[v][o3][o4] = 1;
        }
      }
    }
  }
  __int128_t ret = (__int128_t)1e18 * (__int128_t)1e18;
  for (int i = 1; i <= m; ++i) {
    for (int o1 = 0; o1 < 2; ++o1) {
      for (int o2 = 0; o2 < 2; ++o2) {
        if ((o1 ? u[i] : v[i]) == n) ret = std::min(ret, dis[i][o1][o2]);
      }
    }
  }
  if (ret <= 1e15) std::cout << (int64_t)ret << '\n';
  else std::cout << "-1\n";
}

void dickdreamer() {
  std::cin >> n >> m;
  cnt = m;
  for (int i = 1; i <= n; ++i) idx[i] = ++cnt;
  for (int i = 1; i <= m; ++i) {
    std::cin >> u[i] >> v[i] >> c[i] >> w[i];
    val[u[i]][c[i]] += w[i], val[v[i]][c[i]] += w[i];
    if (!id[u[i]].count(c[i])) id[u[i]][c[i]] = ++cnt;
    if (!id[v[i]].count(c[i])) id[v[i]][c[i]] = ++cnt;
  }
  for (int i = 1; i <= m; ++i) {
    int a = id[u[i]][c[i]], b = id[v[i]][c[i]];
    G[i][0][0].emplace_back(idx[v[i]], 0, 0, 0);
    G[i][0][1].emplace_back(idx[v[i]], 0, 0, 0);
    G[i][0][1].emplace_back(id[v[i]][c[i]], 0, 0, -w[i]);

    G[i][1][0].emplace_back(idx[u[i]], 0, 0, 0);
    G[i][1][1].emplace_back(idx[u[i]], 0, 0, 0);
    G[i][1][1].emplace_back(id[u[i]][c[i]], 0, 0, -w[i]);

    G[idx[u[i]]][0][0].emplace_back(i, 0, 0, val[u[i]][c[i]] - w[i]);
    G[idx[u[i]]][0][0].emplace_back(i, 0, 1, w[i]);

    G[idx[v[i]]][0][0].emplace_back(i, 1, 0, val[v[i]][c[i]] - w[i]);
    G[idx[v[i]]][0][0].emplace_back(i, 1, 1, w[i]);

    G[id[u[i]][c[i]]][0][0].emplace_back(i, 0, 0, val[u[i]][c[i]] - w[i]);
    G[id[v[i]][c[i]]][0][0].emplace_back(i, 1, 0, val[v[i]][c[i]] - w[i]);
  }
  // dijkstra();
  spfa();
}

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;
}