#include <fstream>
#include <limits>
#include <queue>
#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();
//const int INF = 1e9 + 7;

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

    vector<Distance> bellmanFord(Node s) {
        vector<Distance> distFromS(nodeCount, INF);
        std::queue<Node> relaxQueue;
        vector<bool> isInQueue(nodeCount, false);

        distFromS[s] = 0;
        relaxQueue.push(s);
        isInQueue[s] = true;

        while (!relaxQueue.empty()) {
            Node n = relaxQueue.front();
            relaxQueue.pop();
            isInQueue[n] = false;

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

                auto newCost = distFromS[n] + edgeCosts[n][next];
                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 edgeFlows[from][to] == edgeCapacities[from][to];
    }

    vector<Distance> dijkstra(Node s,
                              Node t,
                              vector<Distance> &johnsonCost,
                              vector<Node> &prevInPath) {
        prevInPath.assign(nodeCount, -1);
        vector<Distance> originalDist(nodeCount, INF);
        vector<Distance> positiveDist(nodeCount, INF);

        std::priority_queue<std::pair<Cost, Node>, std::vector<std::pair<Cost, Node>>, std::greater<>>
                minDistNodes;
        // Lazy deletion in priority_queue
        vector<bool> isVisited(nodeCount, false);

        minDistNodes.emplace(0, s);
        originalDist[s] = 0;
        positiveDist[s] = 0;

        auto getJohnsonCost = [&](Node from, Node to) -> Cost {
            return edgeCosts[from][to] + johnsonCost[from] - johnsonCost[to];
        };

        while (!minDistNodes.empty()) {
            Node minNode = minDistNodes.top().second;
            minDistNodes.pop();
            if (isVisited[minNode]) continue;
            isVisited[minNode] = true;

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

                auto newDist =
                        positiveDist[minNode] + getJohnsonCost(minNode, next);
                if (newDist < positiveDist[next]) {
                    positiveDist[next] = newDist;
                    originalDist[next] = originalDist[minNode] + edgeCosts[minNode][next];
                    prevInPath[next] = minNode;

                    minDistNodes.emplace(positiveDist[next], next);
                }
            }
        }

        return originalDist;
    }

    /// 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,
                            edgeCapacities[prevNode][current] -
                            edgeFlows[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];
            edgeFlows[prev][current] += flow;
            edgeFlows[current][prev] -= flow;
            current = prev;
        }
    }

    /// Try to find an augmenting path and return the added flow and the cost
    FlowCostPair
    tryAugmentFlow(Node s,
                   Node t,
                   vector<Distance> &johnsonCost,
                   vector<Node> &prevInPath) {
        auto originalDist = dijkstra(s, t, johnsonCost, prevInPath);

        auto costToT = originalDist[t];
        if (costToT == INF) {
            return {0, INF};
        }

        // Update the flows through the path
        auto flow = findMinFlowThroughPath(s, t, prevInPath);
        updateFlowThroughPath(s, t, prevInPath, flow);

        // The Johnson costs have changed to the costs that Dijkstra computed
        johnsonCost = std::move(originalDist);

        return {flow, flow * costToT};
    }

public:
    explicit FlowNetwork(int nodeCount) : nodeCount(nodeCount) {
        edgeCapacities.resize(nodeCount, vector<Capacity>(nodeCount));
        edgeFlows.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);
        edgeCapacities[from][to] = capacity;
        edgeCosts[from][to] = cost;
        edgeCosts[to][from] = -cost;
    }

    Cost computeMaxFlowMinCost(Node s, Node t) {
        vector<Distance> johnsonCost = bellmanFord(s);

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

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

        return 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;
        Cost cost;
        fin >> from >> to >> cap >> cost;
        network.addEdge(from, to, cap, cost);
    }
    fin.close();

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

    return 0;
}