Untitled

#include <deque>
#include <ios>
#include <iostream>
#include <queue>
#include <vector>

struct edge_type {
  int64_t capacity;
  int64_t cost;
  int64_t flow{0};

  edge_type(int64_t capacity, int64_t cost) : capacity(capacity), cost(cost) {}
};

struct vertex_type {
  uint32_t to;
  uint32_t edge;

  vertex_type(uint32_t to, uint32_t edge) : to(to), edge(edge) {}
  vertex_type() : to(UINT32_MAX), edge(UINT32_MAX) {}
};

struct graph_type {
  uint32_t s;
  uint32_t t;

  std::vector<std::vector<vertex_type>> vertexes;
  std::vector<edge_type> edges;

  std::vector<uint32_t> distance;
  std::vector<vertex_type> parent;
  std::vector<uint8_t> id;

  void add_edge(uint32_t from, uint32_t to, int64_t capacity, int64_t cost) {
    // std::cout << "from: " << from << ", to: " << to << ", capacity: " <<
    // capacity << ", cost: " << cost << "\n";
    uint32_t direct_edge = edges.size();
    edges.emplace_back(capacity, cost);
    vertexes[from].emplace_back(to, direct_edge);

    uint32_t reverse_edge = edges.size();
    edges.emplace_back(0, -cost);
    vertexes[to].emplace_back(from, reverse_edge);
  }

  int64_t min_cost() {
    int64_t min_cost = 0;

    std::deque<uint32_t> queue;

    while (true) {
      std::fill(distance.begin(), distance.end(), INT32_MAX);
      std::fill(parent.begin(), parent.end(), vertex_type());
      std::fill(id.begin(), id.end(), 0);

      distance[0] = 0;
      queue.push_back(0);

      while (!queue.empty()) {
        uint32_t v = queue.front();
        queue.pop_front();
        id[v] = 2;

        for (const auto &vertex : vertexes[v]) {
          const auto &edge = edges[vertex.edge];

          if (edge.flow < edge.capacity &&
              distance[vertex.to] > (distance[v] + edge.cost)) {
            distance[vertex.to] = distance[v] + edge.cost;

            if (id[vertex.to] == 0) {
              queue.push_back(vertex.to);
            } else if (id[vertex.to] == 2) {
              queue.push_front(vertex.to);
            }

            id[vertex.to] = 1;
            parent[vertex.to].to = v;
            parent[vertex.to].edge = vertex.edge;
          }
        }
      }

      int64_t flow = INT64_MAX;

      if (distance[t] == INT32_MAX) {
        break;
      }

      for (uint32_t v = t; v != 0; v = parent[v].to) {
        const auto &edge = edges[parent[v].edge];
        flow = std::min(flow, edge.capacity - edge.flow);
      }

      for (uint32_t v = t; v != 0; v = parent[v].to) {
        auto &edge = edges[parent[v].edge];
        auto &reverse_edge = edges[parent[v].edge + 1];

        edge.flow += flow;
        reverse_edge.flow -= flow;

        min_cost += edge.cost;
      }
    }

    return min_cost;
  }
};

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

  int n, m;
  std::cin >> n;
  std::cin >> m;

  graph_type graph;
  graph.vertexes.resize(n);
  graph.distance.resize(n);
  graph.id.resize(n);
  graph.parent.resize(n, vertex_type());

  graph.t = n - 1;


    uint32_t from, to;
    int64_t capacity, cost;

    for (int i = 0; i < m; ++i) {
        std::cin >> from;
        std::cin >> to;
        std::cin >> capacity;
        std::cin >> cost;

        graph.add_edge(from - 1, to - 1, capacity, cost);
    }


  std::cout << graph.min_cost() << "\n";
  return 0;
}