#include <iostream>
#include <fstream>
#include <vector>
#include <bitset>
#include <queue>
using namespace std;
ifstream in("fmcm.in");
ofstream out("fmcm.out");
const int maxn = 1005;
int dist[maxn];
struct muchie {
int nod;
int vec;
int flux;
int cap;
int cost;
int costorig;
};
vector <muchie> orig[maxn];
vector <muchie> v[maxn];
muchie tata[maxn];
class cmp
{
public:
bool operator() (pair <int, int> a, pair <int, int> b)
{
return a.second > b.second;
}
};
priority_queue <pair <int, int>, vector <pair <int, int> >, cmp> pq;
int n, s, d;
bool bfs()
{
for(int i = 1; i <= n; i++)
{
dist[i] = (1 << 30);
tata[i] = {0, 0, 0, 0, 0};
}
dist[s] = 0;
pq.push(make_pair(s, 0));
while(!pq.empty())
{
int nod = pq.top().first;
pq.pop();
for(auto it : v[nod])
{
if(dist[it.vec] > dist[nod] + it.cost && it.flux < it.cap) /// pot trimite flux pe aici
{
dist[it.vec] = dist[nod] + it.cost;
tata[it.vec] = it;
pq.push(make_pair(it.vec, dist[it.vec]));
}
}
}
if(dist[d] != (1 << 30))
return 1;
return 0;
}
vector <muchie> drum;
queue <int> q;
bitset <maxn> incoada;
void transforma_graf()
{
/// bellman ford pentru a calcula distantele de la sursa la toate nodurile
for(int i = 1; i <= n; i++)
dist[i] = (1 << 30);
dist[s] = 0;
incoada[s] = 1;
q.push(s);
while(!q.empty())
{
int nod = q.front();
//cerr << nod << "\n";
q.pop();
incoada[nod] = 0;
for(auto it : orig[nod])
{
if(dist[it.vec] > dist[nod] + it.cost)
{
dist[it.vec] = dist[nod] + it.cost;
if(!incoada[it.vec])
{
incoada[it.vec] = 1;
q.push(it.vec);
}
}
}
}
/// inlocuiesc costurile fiecarei muchii (x, y) de cost c cu c + dist[x] - dist[y] si nu pun intrebari
for(int i = 1; i <= n; i++)
for(int j = 0; j < orig[i].size(); j++)
orig[i][j].cost = orig[i][j].cost + dist[i] - dist[orig[i][j].vec];
/// acum orig e graful original cu costurile muchiilor modificare, trebuie sa construiesc v
for(int i = 1; i <= n; i++)
{
for(auto it : orig[i])
{
/// am o muchie (i, it.vec)
v[i].push_back(it);
v[it.vec].push_back({it.vec, i, 0, 0, -it.cost, it.costorig});
}
}
}
vector <muchie> luate; /// muchiile luate in flux
int main()
{
int m;
in >> n >> m >> s >> d;
for(int i = 1; i <= m; i++)
{
int x, y, cap, cost;
in >> x >> y >> cap >> cost;
orig[x].push_back({x, y, 0, cap, cost, cost});
}
transforma_graf();
while(bfs()) /// cat timp gasesc un drum de la 1 la n
{
int act = d;
drum.clear();
while(tata[act].nod != 0)
{
drum.push_back(tata[act]);
act = tata[act].nod;
}
int posibil = (1 << 30); /// fluxul maxim pe care il pot trimite pe drumul gasit
for(auto it : drum) /// calculez ce flux pot trimite
posibil = min(posibil, it.cap - it.flux);
for(auto m : drum) /// scad si adun fluxul pe care il bag din toate muchiile
{
int x = m.nod;
int y = m.vec;
for(int i = 0; i < v[x].size(); i++) /// gasesc muchia (x, y) si adun fluxul bagat
{
if(v[x][i].vec == y)
{
v[x][i].flux += posibil;
break;
}
}
for(int i = 0; i < v[y].size(); i++)
{
if(v[y][i].vec == x)
{
v[y][i].flux -= posibil; /// gasesc muchia (y, x) si scad fluxul bagat
break;
}
}
}
}
int total = 0;
for(int i = 1; i <= n; i++) /// gasesc muchiile pe care am bagat flux
for(auto it : v[i])
if(it.flux > 0)
total = total + it.costorig * it.flux;
out << total << "\n";
return 0;
}