#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <fstream>
using namespace std;
  
const string file = "fmcm";
  
const string infile = file + ".in";
const string outfile = file + ".out";

vector<vector<int> > Cap;
vector<vector<int> > Cost;

vector<vector<int> > G;

vector<int> potential;
vector<int> pozitiveD;
vector<int> realDist;

vector<int> dijParent;

priority_queue<pair<int, int>, vector<pair<int, int> >, greater<pair<int, int> > > heap;

int N, M, S, D;
int MinCost;

const int INF = 0x3f3f3f3f;

void Bellman()
{
	potential.resize(N + 1, INF);
	queue<int> Q;
	vector<bool> inQ(N + 1, false);

	Q.push(S);
	potential[S] = 0;
	while(Q.empty() == false)
	{
		int current = Q.front();
		Q.pop();
		inQ[current] = false;
		for(vector<int>::iterator itr = G[current].begin();
			itr != G[current].end();
			itr++)
		{

			if(Cap[current][*itr] > 0 )
			{
				if(potential[*itr] > potential[current] + Cost[current][*itr])
				{
					potential[*itr] = potential[current] + Cost[current][*itr];
					if(inQ[*itr] == false)
					{
						Q.push(*itr);
						inQ[*itr] = true;
					}
				}
			}
		}
	}
}


bool Dijkstra()
{
	memset(&pozitiveD[0], 0x3f, sizeof(int) * (N + 1));

	realDist[S] = 0;
	pozitiveD[S] = 0;

	heap.push(make_pair(pozitiveD[S], S));

	while(heap.empty() == false)
	{
		int current = heap.top().second;
		heap.pop();
		for(vector<int>::iterator itr = G[current].begin();
			itr != G[current].end();
			itr++)
		{
			if(Cap[current][*itr] > 0)
			{
				int newCost = Cost[current][*itr] + potential[current] - potential[*itr];

				if(pozitiveD[*itr] > pozitiveD[current] + newCost)
				{
					pozitiveD[*itr] = pozitiveD[current] + newCost;
					realDist[*itr] = realDist[current] + Cost[current][*itr];

					heap.push(make_pair(pozitiveD[*itr], *itr));

					dijParent[*itr] = current;

				}
			}
		}
	}
	memcpy(&potential[0], &realDist[0], sizeof(int) * (N + 1));

	if(pozitiveD[D] == INF) return false;

	return true;
}

int main()
{
	fstream fin(infile.c_str(), ios::in);

	fin >> N >> M >> S >> D;

	G.resize( N + 1);
	Cap.resize(N + 1, vector<int>(N + 1));
	Cost.resize(N + 1, vector<int>(N + 1));

	for(int i = 0; i < M; i++)
	{
		int x, y, c, z;
		fin >> x >> y >> c >> z;

		G[x].push_back(y);
		G[y].push_back(x);

		Cap[x][y] = c;
		Cap[y][x] = 0;

		Cost[x][y] = z;
		Cost[y][x] = -z;

	}
	fin.close();

	Bellman();

	dijParent.resize(N + 1);
	pozitiveD.resize(N + 1);
	realDist.resize(N + 1);

	while(Dijkstra())
	{
		int maxFlow = INF;
		for(int current = D; current != S; current = dijParent[current])
		{
			 
			maxFlow = min(maxFlow, Cap[dijParent[current]][current]); 
		}

		for(int current = D; current != S; current = dijParent[current])
		{

			Cap[dijParent[current]][current] -= maxFlow;
			Cap[current][dijParent[current]] += maxFlow; 
		}
		
		MinCost += maxFlow * realDist[D];
		cout << MinCost << "\n";
	}

	fstream fout(outfile.c_str(), ios::out);
	fout << MinCost << "\n";
	cout << MinCost << "\n";
	fout.close();
}