#include <fstream>
#include <limits>
#include <queue>
#include <unordered_set>
#include <vector>

using std::vector;
using Node = int;
using Distance = int;
using Cost = int;
using Capacity = int;

using FlowCostPair = std::pair<Capacity, Cost>;

const int INF = std::numeric_limits<Distance>::max();

class FlowNetwork {
private:
    int nodeCount;
    vector<vector<Capacity>> capacityMatrix;
    vector<vector<Capacity>> flowMatrix;
    vector<vector<Cost>> edgeCosts;
    vector<vector<Node>> adjList;

    vector<Distance> bellmanFord(Node s) {
        vector<Distance> distFromS(nodeCount, INF);
        std::queue<Node> relaxQueue;
        relaxQueue.push(s);
        distFromS[s] = 0;

        vector<bool> isInQueue(nodeCount, false);

        while (!relaxQueue.empty()) {
            Node n = relaxQueue.front();
            relaxQueue.pop();

            for (Node next : adjList[n]) {
                auto cost = edgeCosts[n][next];
                auto newCost = distFromS[n] + cost;
                if (newCost < distFromS[next]) {
                    distFromS[next] = newCost;

                    if (!isInQueue[next]) {
                        relaxQueue.push(next);
                        isInQueue[next] = true;
                    }
                }
            }
        }

        return distFromS;
    }

    bool isEdgeSaturated(Node from, Node to) {
        return flowMatrix[from][to] == capacityMatrix[from][to];
    }

    vector<Distance> dijkstra(Node s,
                              Node t,
                              const vector<Distance> &johnsonDist,
                              vector<Node> &prevInPath) {
        prevInPath.assign(nodeCount, -1);
        std::vector<Distance> distance(nodeCount, INF);

        auto closerNode = [&](Node node1, Node node2) {
            return distance[node1] > distance[node2];
        };
        std::priority_queue<Node, std::vector<Node>, decltype(closerNode)>
            minDistNodes(closerNode);
        // Lazy deletion in priority_queue
        std::unordered_set<int> extractedMinNodes;

        minDistNodes.push(s);
        distance[s] = 0;

        /// Extract the min distance node from the Dijkstra queue
        auto extractMinNode = [&]() {
            Node minNode = minDistNodes.top();
            while (extractedMinNodes.find(minNode) != extractedMinNodes.end()) {
                minDistNodes.pop();
                minNode = minDistNodes.top();
            }
            minDistNodes.pop();
            extractedMinNodes.insert(minNode);
            return minNode;
        };

        auto getJohnsonDist = [&](Node from, Node to) {
            return edgeCosts[from][to] + johnsonDist[from] - johnsonDist[to];
        };

        while (!minDistNodes.empty()) {
            Node minNode = extractMinNode();

            for (Node next : adjList[minNode]) {
                if (isEdgeSaturated(minNode, next)) continue;

                auto newDist =
                    distance[minNode] + getJohnsonDist(minNode, next);
                if (newDist < distance[next]) {
                    distance[next] = newDist;
                    prevInPath[next] = minNode;

                    if (next == t) break;

                    minDistNodes.push(next);
                }
            }
        }

        return distance;
    }

    /// Find the minimum capacity through the path from start to end
    int findMinFlowThroughPath(Node start, Node end, vector<Node> &prevInPath) {
        int flow = INF;
        Node current = end;
        while (current != start) {
            Node prevNode = prevInPath[current];
            flow = std::min(flow,
                            capacityMatrix[prevNode][current] -
                                flowMatrix[prevNode][current]);
            current = prevNode;
        }

        return flow;
    }

    /// Update the flows through the path from start to end with the given value
    void updateFlowThroughPath(Node start,
                               Node end,
                               vector<Node> &prevInPath,
                               int flow) {
        Node current = end;
        while (current != start) {
            Node prev = prevInPath[current];
            flowMatrix[prev][current] += flow;
            flowMatrix[current][prev] -= flow;
            current = prev;
        }
    }

    /// Try to find an augmenting path and return the added flow and the cost
    std::pair<Capacity, Cost>
    tryAugmentFlow(Node s,
                   Node t,
                   const vector<Distance> &johnsonDist,
                   vector<Node> &prevInPath) {
        auto distFromS = dijkstra(s, t, johnsonDist, prevInPath);

        if (distFromS[t] == INF) {
            return {0, INF};
        }

        // Join nodeBeforeT and t and update the capacities through the path
        auto minFlowThroughPath = findMinFlowThroughPath(s, t, prevInPath);
        updateFlowThroughPath(s, t, prevInPath, minFlowThroughPath);

        Cost realCost = distFromS[t] - johnsonDist[s] + johnsonDist[t];
        return {minFlowThroughPath, realCost};
    }

public:
    explicit FlowNetwork(int nodeCount) : nodeCount(nodeCount) {
        capacityMatrix.resize(nodeCount, vector<Capacity>(nodeCount));
        flowMatrix.resize(nodeCount, vector<Capacity>(nodeCount));
        adjList.resize(nodeCount);
        edgeCosts.resize(nodeCount, vector<Cost>(nodeCount, 0));
    }

    void addEdge(Node from, Node to, Capacity capacity, Cost cost) {
        adjList[from].push_back(to);
        adjList[to].push_back(from);
        capacityMatrix[from][to] = capacity;
        edgeCosts[from][to] = cost;
        edgeCosts[to][from] = -cost;
    }

    FlowCostPair computeMaxFlowMinCost(Node s, Node t) {
        vector<Distance> johnsonDist = bellmanFord(s);

        Capacity maxFlow = 0;
        Cost minCost = 0;
        vector<Node> prevInPath(nodeCount);

        FlowCostPair augResult = tryAugmentFlow(s, t, johnsonDist, prevInPath);
        while (augResult.first > 0) {
            maxFlow += augResult.first;
            minCost += augResult.second * augResult.first;
            augResult = tryAugmentFlow(s, t, johnsonDist, prevInPath);
        }

        return {maxFlow, minCost};
    }
};

int main() {
    std::ifstream fin("fmcm.in");

    int nodeCount, edgeCount;
    Node s, t;
    fin >> nodeCount >> edgeCount >> s >> t;

    FlowNetwork network(nodeCount + 1);

    for (int i = 0; i < edgeCount; ++i) {
        Node from, to;
        Capacity cap;
        int cost;
        fin >> from >> to >> cap >> cost;
        network.addEdge(from, to, cap, cost);
    }

    fin.close();

    // a)
    std::ofstream fout("fmcm.out");
    fout << network.computeMaxFlowMinCost(s, t).second << '\n';
    fout.close();

    return 0;
}