#include <iostream>
#include <algorithm>
#include <fstream>
#include <functional>
#include <iterator>
#include <limits>
#include <queue>
#include <utility>
#include <vector>
using namespace std;
const int INF = numeric_limits<int>::max();
void bellman_ford(
vector<int>& P,
const int source,
const vector<vector<int>>& cost,
const vector<vector<int>>& capacity,
const vector<vector<int>>& G);
int findResidualCapacity(
int start,
const vector<int>& tree,
const vector<vector<int>>& capacity);
int augmentFlow(
const int residualCapacity,
int start,
const vector<int>& tree,
const vector<vector<int>>& cost,
vector<vector<int>>& capacity);
pair<int, int> minCostMaxFlow(
const int source,
const int sink,
const vector<vector<int>>& cost,
vector<vector<int>>& capacity,
const vector<vector<int>>& G);
int main()
{
ifstream fin("fmcm.in");
ofstream fout("fmcm.out");
int nodes, edges, source, sink;
fin >> nodes >> edges >> source >> sink; source--; sink--;
// residual network
vector<vector<int>> G(nodes),
capacity(nodes, vector<int>(nodes, 0)),
cost(nodes, vector<int>(nodes, 0));
for (int u, v, c, z; edges; --edges)
{
fin >> u >> v >> c >> z; u--; v--;
capacity[u][v] = c;
cost[u][v] = z;
cost[v][u] = -z;
G[u].push_back(v);
G[v].push_back(u);
}
pair<int, int> result = minCostMaxFlow(source, sink, cost, capacity, G);
fout << result.first << endl;
return 0;
}
pair<int, int> minCostMaxFlow(
const int source,
const int sink,
const vector<vector<int>>& cost,
vector<vector<int>>& capacity,
const vector<vector<int>>& G)
{
int minCost = 0, maxFlow = 0, residualCapacity;
vector<int> tree(G.size()); // shortest paths tree
while (true)
{
// find augmenting paths
bellman_ford(tree, source, cost, capacity, G);
// if there are no more paths which reach the sink
if (tree[sink] == -1) break;
residualCapacity = findResidualCapacity(sink, tree, capacity);
minCost += augmentFlow(residualCapacity, sink, tree, cost, capacity);
maxFlow += residualCapacity;
}
return make_pair(minCost, maxFlow);
}
int augmentFlow(
const int residualCapacity,
int start,
const vector<int>& tree,
const vector<vector<int>>& cost,
vector<vector<int>>& capacity) {
int c = 0;
for (; start != tree[start]; start = tree[start]) {
capacity[tree[start]][start] -= residualCapacity;
capacity[start][tree[start]] += residualCapacity;
c += cost[tree[start]][start] * residualCapacity;
}
return c;
}
int findResidualCapacity(
int start,
const vector<int>& tree,
const vector<vector<int>>& capacity) {
int flow = INF;
for (; start != tree[start] && flow; start = tree[start])
flow = min(flow, capacity[tree[start]][start]);
return flow == INF ? 0 : flow;
}
void bellman_ford(
vector<int>& P,
const int source,
const vector<vector<int>>& cost,
const vector<vector<int>>& capacity,
const vector<vector<int>>& G) {
vector<int> D(G.size(), INF);
queue<int> Q;
vector<bool> inQ(G.size(), false);
vector<int> times_inQ(G.size(), 0);
fill(P.begin(), P.end(), -1);
P[source] = source;
D[source] = 0;
Q.push(source);
inQ[source] = true;
times_inQ[source]++;
bool has_negative_cycle = false;
while (!Q.empty() && !has_negative_cycle)
{
int u = Q.front(); Q.pop();
inQ[u] = false;
for (int v : G[u])
if (capacity[u][v] && D[v] > D[u] + cost[u][v]) {
D[v] = D[u] + cost[u][v];
P[v] = u;
if (!inQ[v]) {
Q.push(v);
inQ[v] = true;
times_inQ[v]++;
if (times_inQ[v] >= G.size()) {
has_negative_cycle = true;
break;
}
}
}
}
}