#include <bits/stdc++.h>
#define num int
#define num_mat std::vector <std::vector <std::pair <int, num>>>
#define num_INF 2000000005
int N, M, S, T;
std::vector <std::vector <int>> cap;
std::vector <std::vector <std::pair <int, num>>> graph, graph2;
#define NEGATIVE_EDGE_SUPPORT true
inline void addEdge(int x, int y, int w, int c) {
if (NEGATIVE_EDGE_SUPPORT) graph2[x].push_back({y, w});
graph[x].push_back({y, w});
graph[y].push_back({x, -w});
cap[x][y] = c;
}
class NegativeEdgeDijkstraSupport {
public:
NegativeEdgeDijkstraSupport(num_mat& graph, int src) {
N = graph.size();
dist .resize(graph.size(), 0);
inQueue.resize(graph.size(), false);
bellmanFord(src, graph);
}
int& operator[] (int u) { return dist[u]; }
int& getDistRef (int u) { return dist[u]; }
int calc(int u, int v, int w) { return w + dist[u]-dist[v]; }
private:
void bellmanFord(int src, num_mat& graph) {
for (int i=0; i<N; ++i) dist[i] = num_INF;
queue.push(src);
dist[src] = 0;
inQueue[src] = true;
while (!queue.empty()) {
auto front = queue.front();
queue.pop();
inQueue[front] = false;
for (auto &it:graph[front]) {
if (dist[it.first] > dist[front] + it.second) {
dist[it.first] = dist[front] + it.second;
if (!inQueue[it.first]) inQueue[it.first] = true, queue.push(it.first);
}
}
}
}
int N;
std::vector <int> dist;
std::queue <int> queue;
std::vector <bool> inQueue;
};
class EdmondKarp {
public:
EdmondKarp (num_mat& graph, std::vector <std::vector <int>> cap, int S, int T, num_mat graph2 = num_mat()) { supp = nullptr; calculate(graph, cap, S, T, graph2); }
void calculate(num_mat& graph, std::vector <std::vector <int>> cap, int S, int T, num_mat graph2 = num_mat()) {
if (NEGATIVE_EDGE_SUPPORT) {
if (supp != nullptr) delete supp;
supp = new NegativeEdgeDijkstraSupport(graph2, S);
dist.resize(graph.size());
}
this->S = S, this->T = T, flowCost = flowValue = 0;
rdist .resize(graph.size());
parent.resize(graph.size());
flow .resize(graph.size(), std::vector <int> (graph.size(), 0));
while (dijkstra(graph, cap)) {
int min = num_INF, x = T;
while (x != S)
min = std::min(min, cap[parent[x]][x]-flow[parent[x]][x]), x = parent[x];
if (min <= 0) continue;
x = T;
flowCost += min*rdist[T];
flowValue += min;
while (x != S) flow[x][parent[x]] -= min, flow[parent[x]][x] += min,
x = parent[x];
}
}
inline int getFlowCost() { return flowCost; }
inline int getMaxFlow () { return flowValue; }
private:
bool dijkstra(num_mat& graph, std::vector <std::vector <int>>& cap) {
if (NEGATIVE_EDGE_SUPPORT) dijkstraSupp (graph, cap);
else dijkstraNoSupp(graph, cap);
}
bool dijkstraSupp(num_mat& graph, std::vector <std::vector <int>>& cap) {
for (int i=0; i<N; ++i) dist[i] = rdist[i] = num_INF;
queue.push({0, S});
dist[S] = rdist[S] = 0;
while (!queue.empty()) {
auto top = queue.top(); queue.pop();
if (dist[top.second] < top.first) continue;
for (auto &it:graph[top.second]) {
if (flow[top.second][it.first] < cap[top.second][it.first] && dist[it.first] > dist[top.second] + supp->calc(top.second, it.first, it.second)) {
dist [it.first] = dist[top.second] + supp->calc(top.second, it.first, it.second);
rdist[it.first] = rdist[top.second] + it.second;
parent[it.first] = top.second;
queue.push({dist[it.first], it.first});
}
}
}
for (int i=0; i<N; ++i) supp->getDistRef(i) = rdist[i];
return (dist[T] != num_INF);
}
bool dijkstraNoSupp(num_mat graph, std::vector <std::vector <int>>& cap) {
for (int i=0; i<N; ++i) rdist[i] = num_INF;
queue.push({0, S});
rdist[S] = 0;
while (!queue.empty()) {
auto top = queue.top(); queue.pop();
if (rdist[top.second] < top.first) continue;
for (auto &it:graph[top.second])
if (flow[top.second][it.first] < cap[top.second][top.first] && rdist[it.first] > rdist[top.second] + it.second) {
rdist [it.first] = rdist[top.second] + it.second;
parent[it.first] = top.second;
queue.push({rdist[it.first], it.first});
}
} return (rdist[T] != num_INF);
}
int S, T, flowCost, flowValue;
std::priority_queue <std::pair <int, int>, std::vector <std::pair <int, int>>, std::greater <std::pair <int, int>>> queue;
std::vector <int> parent;
std::vector <int> dist, rdist;
std::vector <std::vector <int>> flow;
NegativeEdgeDijkstraSupport *supp;
};
std::ifstream input ("fmcm.in");
std::ofstream output("fmcm.out");
int main()
{
input >> N >> M >> S >> T;
cap.resize(N, std::vector <int> (N, 0));
graph .resize(N);
graph2.resize(N);
for (int i=1, x, y, c, z; i<=M; ++i)
input >> x >> y >> c >> z, addEdge(x-1, y-1, z, c);
output << (EdmondKarp(graph, cap, S-1, T-1, graph2)).getFlowCost();
return 0;
}