#include <bits/stdc++.h>

#define int int64_t

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

int n, m;
int u[kMaxM], v[kMaxM], c[kMaxM], w[kMaxM];
std::unordered_map<int, int> val[kMaxN];
std::unordered_map<int, std::multiset<int>> mp[kMaxN];

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];
  int &v = val[u][c[a]], &v2 = val[u][c[b]];
  auto &st = mp[u][c[a]], &st2 = mp[u][c[b]];
  if (o1) v -= w[a], st.erase(st.lower_bound(w[a]));
  ret = v2 - w[b];
  if (o1) v += w[a], st.emplace(w[a]);
  return ret;
}

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 dickdreamer() {
  std::cin >> n >> m;
  for (int i = 1; i <= m; ++i) {
    std::cin >> u[i] >> v[i] >> c[i] >> w[i];
    mp[u[i]][c[i]].emplace(w[i]);
    mp[v[i]][c[i]].emplace(w[i]);
    val[u[i]][c[i]] += w[i], val[v[i]][c[i]] += w[i];
  }
  dijkstra();
}

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