#include <iostream>
#include <list>
#include <math.h>
#include <time.h>
#include <string>
#include <fstream>
#include <queue>
#define INF	INT_MAX
#define MAX 20
using namespace std;
class Nod;

class Vecin {
public:
	Nod* v; //nodul vecin
	int cap;
	int cost;
	int flux;
	int rez;
};

class Nod {
public:
	int nume;
	int d; //distanta
	int cul; //culoare
	Nod* p; //parinte
	int nrvec; //numar vecini
	int m;
	int cap; //capacitate de extractie
	bool h; //true daca apartine heapului
	list<Vecin*> vecini; //vecini
	int DFS(Nod** cp, Nod** cu);
};

class Muchie {
public:
	int st; //nod sursa
	int sf; //nod destinatie
	int capacitate; //capacitate muchie
	int cost;
};

class Graf{
public:
	int N; //numar noduri
	int M; //numar muchii
	Nod* sursa;
	Nod* drena;
	list<Muchie> muchii;
	list<Nod*> noduri;
	int citire();
	void adauga_nod(int nume);
	void adauga_vecini(Nod* s);
	void adauga_costuri(Nod* s);
	void adauga_sursa();
	void adauga_drena();
	int gaseste_nod(int nume);
	void afisare();
	int EdmondsKarp(Nod* s, Nod* t, int* costmin);
	int BFS(Nod* s, Nod* t);
	int max_flow_min_cost(int* fmax);
	int Bellman_Ford(Nod* sursa, Nod* drena, int* cost);
};

Graf g;

int Graf::citire(){
	int i, capacitate;
	list<Muchie>::iterator it;
	list<Nod*>::iterator it2;
	int nodst;
	int nodsf;
	int cost;
	int s, d;
	ifstream f ("fmcm.in");
	if (!f) {
		cout << "Deschidere nereusita" << endl;
		return 0;
	}

	f >> this->N;
	f >> this->M;
	f >> s;
	f >> d;
	vector<int> extractie(N);
	for (i=0; i<this->M; i++){
		//citesc o muchie
		f >> nodst;
		f >> nodsf;
		f >> capacitate;
		f >> cost;
		Muchie m;
		m.capacitate = capacitate;
		m.st = nodst;
		m.sf = nodsf;
		m.cost = cost;
		//introduc muchia in graf
		this->muchii.push_back(m);
	}
	f.close();

	//completez reprezentarea cu liste de adiacente a grafului:
	//adaug intai fiecare nod in parte
	for (it = this->muchii.begin(); it != this->muchii.end(); it++){
		this->adauga_nod((*it).st);
		this->adauga_nod((*it).sf);
	}
	//adaug pentru fiecare nod vecinii sai
	for (it2 = this->noduri.begin(); it2 != this->noduri.end(); it2++){
		this->adauga_vecini((*it2));
	}
	//completez nodurilor capacitatea de extractie
	for (it2 = this->noduri.begin(); it2 != this->noduri.end(); it2++){
		(*it2)->cap = extractie[(*it2)->nume - 1];
	}
	//adaug costurile negative pentru muchiile inverse
	for (it2 = this->noduri.begin(); it2 != this->noduri.end(); it2++){
		this->adauga_costuri((*it2));
	}
	//adaug sursa si drena
	for (it2 = this->noduri.begin(); it2 != this->noduri.end(); it2++){
		if ((*it2)->nume == s) this->sursa = (*it2);
		if ((*it2)->nume == d) this->drena = (*it2);
	}
	return 1;
}

int Graf::gaseste_nod(int nume){
	//cauta un nod cu numele nume in graf, intoarce 1 daca il gaseste, 0 altfel
	list<Nod*>::iterator it;
	for (it = this->noduri.begin(); it != this->noduri.end(); it++){
		if ((*it)->nume == nume) return 1;
	}
	return 0;
}

void Graf::adauga_nod(int nume){
	//adauga un nod la graf numai daca nodul nu a mai fost introdus o data
	if (this->gaseste_nod(nume) == 0){
		Nod* n = new Nod();
		n->nume = nume;
		n->nrvec = 0;
		n->cul = 0;
		n->m = 0;
		n->h = true;
		this->noduri.push_back(n);
	}
}

void Graf::adauga_vecini(Nod* s){
	list<Nod*>::iterator it;
	list<Muchie>::iterator it2;
	//adaug pentru fiecare nod toate nodurile ca vecini;
	//pentru cei care de fapt nu sunt vecini, capacitatea muchiei va fi 0
	for (it = this->noduri.begin(); it != this->noduri.end(); it++){
		bool ok = false;
		for (it2 = this->muchii.begin(); it2 != this->muchii.end(); it2++){
			if (((*it2).st == s->nume) && ((*it2).sf == (*it)->nume)) {
				ok = true;
				break;
			}
		}
		Vecin* vec = new Vecin();
		vec->v = (*it);
		if (ok){
			vec->cap = (*it2).capacitate;
			vec->cost = (*it2).cost;
		} else {
			vec->cap = 0;
		}
		vec->flux = 0;
		s->vecini.push_back(vec);
		s->nrvec++;
	}
}

void Graf::adauga_costuri(Nod* s){
	//adauga costuri negative pentru muchiile inverse
	list<Nod*>::iterator it;
	list<Vecin*>::iterator it2, it3;
	for (it = this->noduri.begin(); it != this->noduri.end(); it++){
		for (it2 = (*it)->vecini.begin(); it2 != (*it)->vecini.end(); it2++){
			if ((*it2)->cost != 0){
				for (it3 = (*it2)->v->vecini.begin(); it3 != (*it2)->v->vecini.end(); it3++){
					if ((*it3)->v->nume == (*it)->nume){
						(*it3)->cost = (*it2)->cost * (-1);
						break;
					}
				}
			}
		}
	}
}

void Graf::adauga_sursa(){
	//adaug sursa virtuala
	Nod* sursa = new Nod();
	sursa->nume = 0;
	sursa->cap = INF;
	sursa->nrvec = 0;
	sursa->cul = 0;
	sursa->m = 0;
	sursa->h = true;

	list<Nod*>::iterator it;
	for (it = this->noduri.begin(); it != this->noduri.end(); it++){
		if ((*it)->cap > 0){
			Vecin* vec = new Vecin();
			vec->v = (*it);
			vec->cap = (*it)->cap;
			vec->cost = 0;
			vec->flux = 0;
			sursa->vecini.push_back(vec);
			sursa->nrvec++;
		}
	}
	this->noduri.push_back(sursa);
	this->sursa = sursa;
}

void Graf::adauga_drena(){
	//adaug drena virtuala
	Nod* drena = new Nod();
	drena->nume = this->N + 1;
	drena->cap = -INF;
	drena->nrvec = 0;
	drena->cul = 0;
	drena->m = 0;
	drena->h = true;

	list<Nod*>::iterator it;
	for (it = this->noduri.begin(); it != this->noduri.end(); it++){
		if ((*it)->cap < 0){
			Vecin* vec = new Vecin();
			vec->v = drena;
			vec->cap = (*it)->cap * (-1);
			vec->cost = 0;
			vec->flux = 0;
			(*it)->vecini.push_back(vec);
			(*it)->nrvec++;
		}
	}
	this->noduri.push_back(drena);
	this->drena = drena;
}

void Graf::afisare(){
	//afiseaza graful
	list<Nod*>::iterator it1;
	list<Vecin*>::iterator it2;
	for (it1 = this->noduri.begin(); it1 != this->noduri.end(); it1++){
		cout << (*it1)->nume << ": "  << (*it1)->cap << " ";
		for (it2 = (*it1)->vecini.begin(); it2 != (*it1)->vecini.end(); it2++){
			cout << "(" << (*it2)->v->nume << " " << (*it2)->flux << "/" << (*it2)->cap << " " << (*it2)->cost << ") ";
		}
		cout << endl;
	}
	cout << "---------------------------------------------------------------------------" << endl;
}

int Graf::EdmondsKarp(Nod* s, Nod* t, int* costmin){
    int f = 0, m, aux = 0;
    list<Vecin*>::iterator it;
    Nod *v, *u;
    while(1){
    	//caut un nou drum de ameliorare
    	int cost;
    	m = Bellman_Ford(s, t, &cost);
        if (m == 0) break; //daca nu am mai gasit drum de ameliorare ma opresc
        f = f + m; //adaug la fluxul total fluxul gasit pe noul drum
        v = t;
        while (v != s) {
            u = v->p;

            //pentru fiecare muchie din drum actualizez fluxul
            //F[u->nume -1][v->nume -1] += m;
            for (it = u->vecini.begin(); it != u->vecini.end(); it++){
            	if ((*it)->v == v){
            		(*it)->flux += m;
            		break;
            	}
            }
           // F[v->nume -1][u->nume -1] -= m;
            for (it = v->vecini.begin(); it != v->vecini.end(); it++){
            	if ((*it)->v == u){
            		(*it)->flux -= m;
            		break;
            	}
            }
            v = u;
        }
        aux += cost;
    }
    *costmin = aux;
    return f;
}

int Graf::Bellman_Ford(Nod* sursa, Nod* drena, int* cost){
	//gaseste drumul minim de la sursa la restul nodurilor din componenta conexa din care face parte;
	//determina daca exista cicluri negative in graf
	//complexitate O(N * M)
	list<Nod*>::iterator ii, ij;
	list<Vecin*>::iterator ik;

	//initializari:
	for (ii = this->noduri.begin(); ii != this->noduri.end(); ii++){
		(*ii)->d = INF/2;
		(*ii)->p = NULL;
	}
	sursa->m = INF;
	//distanta de la vecinii imediati ai sursei pana la sursa este costul muchiei
	//parintele vecinilor imediati ai sursei este chiar sursa
	for (ik = sursa->vecini.begin(); ik != sursa->vecini.end(); ik++){
		(*ik)->v->d = (*ik)->cost;
		(*ik)->v->p = sursa;
	}
	//sursa are distanta 0 pana la ea, si nu are parinte
	sursa->d = 0;
	sursa->p = NULL;

	//relaxari succesive: O(N * M)
	//int stop = 0;
	for (ii = this->noduri.begin(); ii != this->noduri.end(); ii++){
		for (ij = this->noduri.begin(); ij != this->noduri.end(); ij++){
			for (ik = (*ij)->vecini.begin(); ik != (*ij)->vecini.end(); ik++){
				if ((*ik)->cap - (*ik)->flux > 0){ //daca exista muchia in graful rezidual
					if ((*ik)->v->d > (*ij)->d + (*ik)->cost){
						(*ik)->v->d = (*ij)->d + (*ik)->cost;
						(*ik)->v->p = (*ij);
					}
				}
			}
		}
	}
	//am gasit drum de ameliorare
	if (this->drena->d < INF/2){
		int fmin = INF;
		list<Vecin*>::iterator it;
		Nod* i = this->drena;
		while (i != this->sursa){
			Nod* p = i->p;
			for (it = p->vecini.begin(); it != p->vecini.end(); it++){
				if ((*it)->v == i){
					if ((*it)->cap - (*it)->flux < fmin){
						fmin = (*it)->cap - (*it)->flux;
					}
					break;
				}
			}
			i = p;
		}
		*cost = fmin * this->drena->d;
		return fmin;
	}
	*cost = 0;
	return 0;
}

int Graf::max_flow_min_cost(int* fmax){
	int costmin;
	*fmax = this->EdmondsKarp(this->sursa, this->drena, &costmin);
	return costmin;
}

int main(){
    list<Nod*>::iterator i;
    list<Vecin*>::iterator it;
    int fmax, costmin, j;

	if (g.citire() == 0) {
		cout << "Eroare la citire" << endl;
		return -1;
	}
	costmin = g.max_flow_min_cost(&fmax);

	ofstream f ("retea.out");
	f << fmax << endl;
	f << costmin << endl;
	for (j = 1; j <= g.N; j++){
		for (i = g.noduri.begin(); i != g.noduri.end(); i++){
			if ((*i)->nume == j){
				for (it = (*i)->vecini.begin(); it != (*i)->vecini.end(); it++){
					if ((*it)->flux > 0 && ((*it)->v->nume != g.N + 1)){
						f << (*i)->nume << " " << (*it)->v->nume << " " << (*it)->flux << endl;
					}
				}
				break;
			}
		}
	}
	f.close();
	return 0;
}