/*
 * e_032_max_flow_min_cost_diskstra_matrices.cpp
 *
 *  Created on: May 29, 2015
 *      Author: Marius
 */

#include <iostream>
#include <utility>
using namespace std;
#include <fstream>
#include <queue>
#include <list>
#include <vector>
#include <string>
#include <algorithm>
#include <limits>
#include <set>

#ifdef __BLOCK_TIMERS
#include "util/BlockTimer.h"
#else
class BlockTimerC
{
public:
    BlockTimerC(std::string a) : a(a)
    {}
protected:
    std::string a;
};
#endif

namespace e_032_max_flow_min_dijsktra_matrices_nms
{
    const int MAX_N = 350;
    int cap[MAX_N + 1][MAX_N + 1];
    int cst[MAX_N + 1][MAX_N + 1];

    void find_best_cost_bellman_ford(int S, vector<vector<int>>& adj_list, vector<int>& best_cost)
    {
        int N = adj_list.size() - 1;
        list<int> Q;
        vector<char> in_queue;
        in_queue.resize(N + 1);

        std::fill(best_cost.begin(), best_cost.end(), std::numeric_limits<int>::max());
        std::fill(in_queue.begin(), in_queue.end(), 0);

        Q.push_back(S);
        in_queue[S] = 1;
        best_cost[S] = 0;

        //while ( !Q.empty() && max_bfs_level <= N )
        // the problem statement guarantees there are no negative cycles
        while (!Q.empty())
        {
            // pop one element from the list
            int u = Q.front();
            Q.pop_front();
            in_queue[u] = 0;

            //parse the adjacency list and look for possible better costs
            for (auto v : adj_list[u])
            {
                if (cap[u][v] <= 0) continue; //only positive capacities are processed here

                int candidate_cost = best_cost[u] + cst[u][v];
                if (candidate_cost < best_cost[v])
                {
                    best_cost[v] = candidate_cost;
                    if (!in_queue[v])
                    {
                        Q.push_back(v);
                        in_queue[v] = 1;
                    }
                }
            }

        }
    }

    int find_max_flow_ford_fulkerson(int N, int S, int D, vector<vector<int>>& adj_list,
            int& total_cost)
    {
        int max_flow = 0;
        total_cost = 0;

        //find the initial best cost using the bellman ford algorithm
        //the algorithm only uses the cost and ignores the capacities of the edges
        vector<int> best_cost_prev, best_cost_new;
        best_cost_prev.resize(N + 1);
        best_cost_new.resize(N + 1);

        find_best_cost_bellman_ford(S, adj_list, best_cost_prev);

        typedef pair<int, int> p_ii;
        priority_queue<p_ii, vector<p_ii>, std::greater<p_ii>> Q;
        vector<int> best_cost_augmented;
        vector<char> in_queue;
        vector<int> parents;

        best_cost_augmented.resize(N + 1);
        in_queue.resize(N + 1);
        parents.resize(N + 1);

        std::fill(best_cost_new.begin(), best_cost_new.end(), std::numeric_limits<int>::max() / 2);

        bool has_s2t_path = true;
        while (has_s2t_path)
        {
            //Dijkstra
            std::fill(best_cost_augmented.begin(), best_cost_augmented.end(),
                    std::numeric_limits<int>::max() / 2);

            best_cost_augmented[S] = 0;
            best_cost_new[S] = 0;

            for (int u = 1; u <= N; u++)
                Q.push(make_pair(best_cost_augmented[u], u));

            std::fill(in_queue.begin(), in_queue.end(), 1);

            for (auto& p : parents)
                p = 0;

            //find a path from source to sink in the residual graph
            //only edges with positive capacities should be included in the path
            while (!Q.empty())
            {
                //pop the first element in the set
                auto top = Q.top();
                int u = top.second;
                int bu = top.first;
                Q.pop();

                //if not the true minimum, do nothing
                //take care about multiple costs for the same node in the priority queue
                if (bu > best_cost_augmented[u]) continue;

                in_queue[u] = 0; // no longer in queue

                for (int v : adj_list[u])
                {
                    //edge with positive capacity
                    int cap_uv = cap[u][v], cst_uv = cst[u][v];
                    if (in_queue[v] == 1 && cap_uv > 0)
                    {
                        //check-update the cost of the node
                        int augmented_cost_uv = best_cost_augmented[u] + cst_uv + best_cost_prev[u]
                                - best_cost_prev[v];

                        if (augmented_cost_uv < best_cost_augmented[v])
                        {
                            //update the cost of the node                           
                            best_cost_augmented[v] = augmented_cost_uv;

                            //insert the updated cost
                            //take care, the previous best cost, is still in the priority queue
                            Q.push(make_pair(best_cost_augmented[v], v));

                            parents[v] = u;

                            //update the real best cost
                            best_cost_new[v] = best_cost_new[u] + cst_uv;
                        }
                    }
                }
            }

            //prepare the updated cost for the next iteration
            //for (int i = 1; i <= N; i++)
            //best_cost_prev[i] = best_cost_new[i];
            best_cost_prev = best_cost_new;

            //if the sink was reached, there is a path from source to sink
            //the path is the shortest, due to the bellman-ford algorithm
            if (parents[D] != 0)
            {
                // we have a path from source to sink
                // update the residual graph
                //
                // parse the path we have found from sink to source, via parent edges
                // and find the minimum capacity
                int min_capacity = cap[parents[D]][D] + 1;
                int node = D;
                while (node != S)
                {
                    int p = parents[node];
                    min_capacity = min(min_capacity, cap[p][node]);
                    node = p;
                }
                //increment the flow value
                max_flow += min_capacity;

                //update the capacity of edges in the residual graph
                node = D;
                while (node != S)
                {
                    int p = parents[node];
                    cap[p][node] -= min_capacity;
                    //also update the reverse edge
                    cap[node][p] += min_capacity;

                    //update the total cost
                    total_cost += min_capacity * cst[p][node];

                    node = p; //go to the parent node
                }
            }
            else
                has_s2t_path = false; //no more paths from s to t
        }

        return max_flow;
    }
}

//int e_032_max_flow_min_dijsktra_matrices()
int main()
{
    using namespace e_032_max_flow_min_dijsktra_matrices_nms;

    string in_file = "fmcm.in";
    string out_file = "fmcm.out";

    int N, M, S, D;
    vector<vector<int>> adj_list;

    {
        BlockTimerC bc("Inputs");
        ifstream ifs(in_file.c_str());
        if (!ifs.is_open())
        {
            cout << "Input file not found" << endl;
            return -1; // no input file
        }
        ifs >> N >> M >> S >> D;

        adj_list.resize(N + 1);

        for (int m = 1; m <= M; m++)
        {
            //create the forward and it's backward edge
            int u, v, c, z;
            ifs >> u >> v >> c >> z;
            cap[u][v] = c;
            cst[u][v] = z;

            cap[v][u] = 0;
            cst[v][u] = -z;

            adj_list[u].push_back(v);
            adj_list[v].push_back(u);
        }

        ifs.close();
    }
    
    int total_cost;
    {
        BlockTimerC bc("Algorithm");
        find_max_flow_ford_fulkerson(N, S, D, adj_list, total_cost);
    }
    {
        BlockTimerC bc("Outputs");
        ofstream ofs(out_file.c_str());
        //ofs << max_flow << endl;
        ofs << total_cost;
        ofs.close();
    }

    return 0;
}