//@yukicoder 1301

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
using pll = pair<ll, ll>;
using vl = vector<ll>;
template <class T>
using vec = vector<T>;
template <class T>
using vv = vec<vec<T>>;
template <class T>
using vvv = vv<vec<T>>;
template <class T>
using minpq = priority_queue<T, vector<T>, greater<T>>;
#define rep(i, r) for (ll i = 0; i < (r); i++)
#define reps(i, l, r) for (ll i = (l); i < (r); i++)
#define rrep(i, l, r) for (ll i = (r)-1; i >= l; i--)
#define all(a) (a).begin(), (a).end()
#define sz(a) (ll)(a).size()
template <typename T>
bool chmax(T& a, const T& b) {
  return a < b ? a = b, true : false;
}
template <typename T>
bool chmin(T& a, const T& b) {
  return a > b ? a = b, true : false;
}
#include <bits/extc++.h>

const ll INF = 1e18;

struct MinCostFlow {
  struct Edge {
    ll from, to, rev, cap, cost, flow;
  };
  ll n;
  vv<Edge> ed;
  vl seen;
  vl dist, pi;
  vec<Edge*> par;
  MinCostFlow(ll n) : n(n), ed(n), seen(n), dist(n), pi(n), par(n) {}
  void add_edge(ll from, ll to, ll cap, ll cost) {
    if (from == to) return;
    ed[from].push_back(Edge{from, to, sz(ed[to]), cap, cost, 0});
    ed[to].push_back(Edge{to, from, sz(ed[from]) - 1, 0, -cost, 0});
  }
  void path(ll s) {
    fill(all(seen), 0);
    fill(all(dist), INF);
    dist[s] = 0;
    ll di;
    using Pq = __gnu_pbds::priority_queue<pll>;
    Pq q;
    vec<Pq::point_iterator> its(n);
    q.push({0, s});
    while (!q.empty()) {
      s = q.top().second;
      q.pop();
      seen[s] = 1;
      di = dist[s] + pi[s];
      for (Edge& e : ed[s])
        if (!seen[e.to]) {
          ll val = di - pi[e.to] + e.cost;
          if (e.cap - e.flow > 0 && val < dist[e.to]) {
            dist[e.to] = val;
            par[e.to] = &e;
            if (its[e.to] == q.end()) its[e.to] = q.push({-dist[e.to], e.to});
            else q.modify(its[e.to], {-dist[e.to], e.to});
          }
        }
    }
    rep(i, n) pi[i] = min(pi[i] + dist[i], INF);
  }
  pll maxflow(ll s, ll t, ll f = INF) {
    // ll totflow = 0, totcost = 0;
    // while (path(s), totflow < f && seen[t]) {
    //   ll fl_path = INF;
    //   for (Edge* x = par[t]; x; x = par[x->from])
    //     fl_path = min(fl_path, x->cap - x->flow);
    //   ll fl = min(fl_path, f - totflow);
    //   totflow += fl;
    //   for (Edge* x = par[t]; x; x = par[x->from]) {
    //     x->flow += fl;
    //     ed[x->to][x->rev].flow -= fl;
    //   }
    // }
    // rep(i, n) for (Edge& e : ed[i]) totcost += e.cost * e.flow;
    // return {totflow, totcost / 2};
    return slope(s, t, f).back();
  }
  void setpi(ll s) {
    fill(all(pi), INF);
    pi[s] = 0;
    ll it = n, ch = 1;
    ll v;
    while (ch-- && it--)
      rep(i, n) if (pi[i] != INF) for (Edge& e : ed[i]) if (e.cap) if ((v = pi[i] + e.cost) < pi[e.to]) pi[e.to] = v, ch = 1;
    assert(it >= 0);
  }

  vec<pll> slope(ll s, ll t, ll f = INF) {
    vec<pll> res;
    ll totflow = 0, totcost = 0;
    res.push_back({0, 0});
    while (totflow < f && (path(s), seen[t])) {
      ll fl = INF;
      for (Edge* x = par[t]; x; x = par[x->from])
        fl = min(fl, x->cap - x->flow);
      fl = min(fl, f - totflow);

      for (Edge* x = par[t]; x; x = par[x->from]) {
        x->flow += fl;
        ed[x->to][x->rev].flow -= fl;
      }
      ll d = pi[t];
      totflow += fl;
      totcost += fl * d;
      res.push_back({totflow, totcost});
    }
    return res;
  }
};

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  ll n, m;
  cin >> n >> m;

  MinCostFlow mcf(n);

  rep(i, m) {
    ll u, v, c, d;
    cin >> u >> v >> c >> d;
    u--, v--;
    mcf.add_edge(u, v, 1, c);
    mcf.add_edge(v, u, 1, c);
    mcf.add_edge(u, v, 1, d);
    mcf.add_edge(v, u, 1, d);
  }

//   auto mcf2 = mcf;
//   auto mcf3 = mcf;
  cout << mcf.maxflow(0, n-1, 2).second << endl;
//   auto res1 = mcf3.maxflow(0, n-1);
//   cout << res1.first << " " << res1.second;

//   auto res = mcf2.slope(0, n-1);
//   for(auto e : res) {
//     cout << e.first << " " << e.second << endl;
//   }
}