// Flux maxim de cost minim.cpp : Defines the entry point for the console application.
//

//#include "stdafx.h"
#include "stdio.h"
#include "string.h"

FILE *ff=fopen("fmcm.in", "r");
FILE *g=fopen("fmcm.out", "w");


int n, m, s, d;
int sum;

int cap[3510][3510];
int flux[3510][3510];
int ccost[3510][3510];

// variabile graf rezidual

int grez[3510][3510][2];
int countrez[3510];
int heap[3510];
int poz[3510];
int vpoz[3510];
int vizz[3510];
int ant[3510];
int antdef[3510];


// variabile bellman-ford
int coada[100000];
int sol[3510];
int incd[3510], cd;

struct nod
{
	int x, d;
	struct nod *adr;
};

nod *l[50001];


void add(int x, int y, int d)
{
	nod *p=new nod;
	p->x=y;
	p->d=d;
	p->adr=l[x];
	l[x]=p;
}

void bellmanford()
{

	for (int i=1; i<=n; i++)
	{
		sol[i]=10000000;
	}
	sol[s]=0;

	coada[++cd]=s;
	int i=1;
	while (i<=cd)
	{
		incd[coada[i]]=0;
		nod *p=l[coada[i]];
		while (p!=NULL)
		{
			if (sol[p->x]>sol[coada[i]]+p->d)
			{
				sol[p->x]=sol[coada[i]]+p->d;
				if (!incd[p->x])
				{                                             
					coada[++cd]=p->x;
					incd[p->x]=1;
				}
			}
			p=p->adr;
		}
		i++;
	}
}


void init()
{
	for (int i=1; i<=n; ++i)
	{
		nod *p=l[i];
		while (p!=NULL)
		{
			int y=grez[i][p->x][0];
			grez[i][p->x][1]+=sol[i]-sol[y];

			grez[y][++countrez[y]][0]=i;
			grez[y][countrez[y]][1]=-grez[i][p->x][1];
			cap[y][i]=0;

			p=p->adr;
		}
	}
}


void swap(int i, int j)
{
	int h=heap[i]; heap[i]=heap[j]; heap[j]=h;
	h=poz[i]; poz[i]=poz[j]; poz[j]=h;
	vpoz[poz[i]]=i; vpoz[poz[j]]=j;
}


void upheap(int x)
{
	int tata=x/2;
	int fiu=x;
	while (heap[tata]>heap[fiu] && tata>0)
	{
		swap(tata, fiu);
		fiu=tata;
		tata=fiu/2;
	}
}


void downheap(int x)
{
	int tata=x;
	int fiu=x*2;
	if (fiu<heap[0] && heap[fiu]>heap[fiu+1]) fiu++;
	while (heap[tata]>heap[fiu] && fiu<=heap[0])
	{
		swap(tata, fiu);
		tata=fiu;
		fiu=tata*2;
		if (fiu<heap[0] && heap[fiu]>heap[fiu+1]) fiu++;
	}
}


int dijkstra()
{
	heap[0]=0;
	poz[0]=0;
	memset(vizz, 0, sizeof(vizz)); 
	for (int i=1; i<=n; i++)
	{
		if (i!=s)
		{
			heap[++heap[0]]=1000000;
			poz[++poz[0]]=i;
			vpoz[i]=poz[0];
		}
	}
	int cr=s;
	int sum=0;

	while (vizz[d]!=1 && heap[0]>=0 && sum<1000000)
	{
		antdef[cr]=ant[cr];
		vizz[cr]=1;
		if (vizz[d]==1) 
		{
			antdef[cr]=ant[cr];
			return 1;
		}
		for (int j=1; j<=countrez[cr]; ++j)
		{
			int y=grez[cr][j][0];
			int cost=grez[cr][j][1];
			int c=cap[cr][y];
			int f=flux[cr][y];

			if (!vizz[y] && sum+cost<heap[vpoz[y]] && c>f)
			{
				ant[y]=cr;
				heap[vpoz[y]]=sum+cost;
				upheap(vpoz[y]);
			}
		}
		if (heap[0]>0)
		{
			cr=poz[1];
			sum=heap[1];
			heap[1]=heap[heap[0]];
			poz[1]=poz[heap[0]];
			vpoz[poz[1]]=1;
			heap[0]--;
			downheap(1);
		}
			
	}

	if (vizz[d]==1) 
	{
		antdef[cr]=ant[cr];
		return 1;
	}
	return 0;
}

int minim(int x, int y)
{
	if (x>y) return y;
	return x;
}

void program()
{
	while (dijkstra())
	{
		int fflux=1000000000;
		int auxc=0;
		int aux=d;
		while (aux!=s)
		{
			fflux=minim(fflux, cap[antdef[aux]][aux]-flux[antdef[aux]][aux]);
			auxc+=ccost[antdef[aux]][aux];
			aux=antdef[aux];
		}
		sum+=fflux*auxc;
		
		aux=d;
		while (aux!=s)
		{
			flux[antdef[aux]][aux]+=fflux;
			flux[aux][antdef[aux]]-=fflux;
			aux=antdef[aux];
		}
	}

	fprintf(g, "%d", sum);
}




void read()
{
	fscanf(ff, "%d%d%d%d", &n, &m, &s, &d);
	for (int i=1; i<=m; ++i)
	{
		int x, y, c, cost;
		fscanf(ff, "%d%d%d%d", &x, &y, &c, &cost);
		add(x, y, cost);

		grez[x][++countrez[x]][0]=y;
		grez[x][countrez[x]][1]=cost;
		cap[x][y]=c;
		ccost[x][y]=cost;
	}
}


int main()
{
	read();
	bellmanford();
	init();
	program();

	return 0;
}