#include <bits/stdc++.h>
using namespace std;
struct CostEdge
{
int to;
long long int capacity;
long long int cost;
};
struct MinCostFlow
{
//??
static constexpr long long INF=LLONG_MAX/4;
vector<CostEdge>edges;
vector<vector<int>> outEdges;
vector<long long>potential;
MinCostFlow(int nodeCount) : outEdges(nodeCount), potential(nodeCount, 0) {}
void addEdge(int from, int to, long long capacity, long long cost)
{
outEdges[from].push_back(edges.size());
edges.push_back({to, capacity, cost});
outEdges[to].push_back(edges.size());
edges.push_back({from, 0, -cost});
}
// SPFA
void initPotentials(int source)
{
int n=outEdges.size();
vector<long long>dist(n, INF);
vector<char>inQueue(n, 0);
deque<int>q;
dist[source]=0; q.push_back(source);
while(!q.empty())
{
int v=q.front(); q.pop_front(); inQueue[v]=0;
for(int id : outEdges[v])
{
const CostEdge &e=edges[id];
if(e.capacity>0 && dist[v]+e.cost<dist[e.to])
{
dist[e.to]=dist[v]+e.cost;
if(!inQueue[e.to])
{
inQueue[e.to]=1;
q.push_back(e.to);
}
}
}
}
for(int v=0; v<n; v++)
{
if(dist[v]==INF)
potential[v]=0;
else
potential[v]=dist[v];
}
}
pair<long long, long long> run(int source, int sink, long long maxUnits)
{
int n=outEdges.size();
long long int sent=0, totalCost=0;
while(sent<maxUnits)
{
// We do Dijkstra on reduced prices cost+pi(v)-pi(to) (all>=0)
vector<long long>dist(n, INF);
vector<int> parentEdge(n, -1);
priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<>>pq;
dist[source]=0; pq.push({0, source});
while(!pq.empty())
{
auto [d, v]=pq.top(); pq.pop();
if(d!=dist[v])
continue; // outdated value entry, already smth better
for(int id : outEdges[v])
{
const CostEdge &e=edges[id];
if(e.capacity<=0)
continue;
long long reduced=e.cost+potential[v]-potential[e.to];
if(reduced+dist[v]<dist[e.to])
{
dist[e.to]=dist[v]+reduced;
parentEdge[e.to]=id;
pq.push({dist[e.to], e.to});
}
}
}
if(dist[sink]==INF) // if we cannot reach the sink
break;
for(int v=0; v<n; v++)
{
if(dist[v]<INF)
potential[v]+=dist[v]; // we update the potentials pi+=d
}
long long push=maxUnits-sent; // don t push more that needed
for(int v=sink; v!=source; v=edges[parentEdge[v]^1].to)
push=min(push, edges[parentEdge[v]].capacity); // we search for the bottleneck
for(int v=sink; v!=source; v=edges[parentEdge[v]^1].to)
{
edges[parentEdge[v]].capacity-=push;
edges[parentEdge[v]^1].capacity+=push;
totalCost+=push*edges[parentEdge[v]].cost;
}
sent+=push;
}
return {sent, totalCost};
}
};
int main()
{
ifstream cin ("fmcm.in");
ofstream cout ("fmcm.out");
int n, m, s, d;
cin >> n >> m >> s >> d;
MinCostFlow flux(n+1);
for(int i=1; i<=m; i++)
{
int x, y, c, z;
cin >> x >> y >> c >> z;
flux.addEdge(x, y, c, z);
}
flux.initPotentials(s);
pair<long long, long long>val=flux.run(s, d, LLONG_MAX/4);
cout << val.second << '\n';
return 0;
}