#include <stdio.h>
#include <stdlib.h>

#ifndef DYNARRAY_H_
#define DYNARRAY_H_

typedef int dynamic_array_element;

struct dynamic_array;
typedef struct dynamic_array *DynamicArray;

DynamicArray DA_New();
void DA_Delete(DynamicArray *ptrDA);

int DA_Size(DynamicArray DA);
dynamic_array_element* DA_GetVector(DynamicArray DA);
dynamic_array_element DA_Get(DynamicArray DA, int index);
void DA_Insert(DynamicArray DA, dynamic_array_element x);
void DA_Reverse(DynamicArray DA);

#endif /*DYNARRAY_H_*/

// Implementare (minimala) a unui Array Dinamic (care-si modifica lungimea automat).
// Am folosit asa ceva din comoditate, pentru ca n-aveam chef sa
// estimez lungimile unor vectori folositi in solutia mea.

#include <malloc.h>
// Structura contine urmatoarele:
// -> size: marimea utilizata a Array-ul Dinamic
// -> capacity: cat pot baga efectiv in Array
// -> array: vectorul propriu-zis
struct dynamic_array {
	int size, capacity;
	dynamic_array_element *array;
};

// Functia de alocare a unui nou Array Dinamic
DynamicArray DA_New() {
	DynamicArray DA;
	
	DA = (DynamicArray) malloc(sizeof(struct dynamic_array));
	DA->size = 0;
	DA->capacity = 10;
	DA->array = (dynamic_array_element*) malloc(DA->capacity * sizeof(dynamic_array_element));
	
	return DA;
}

// Functia de stergere a unui Array Dinamic
void DA_Delete(DynamicArray *ptrDA) {
	free((*ptrDA)->array);
	free(*ptrDA);
	*ptrDA = NULL;
}

// Intoarce lungimea utilizata a Array-ului
int DA_Size(DynamicArray DA) {
	return DA->size;
}

// Intoarce vectorul folosit de Array-ul Dinamic
dynamic_array_element* DA_GetVector(DynamicArray DA) {
	return DA->array;
}

// Intoarce elementul de la pozitia "index" a Array-ul Dinamic
dynamic_array_element DA_Get(DynamicArray DA, int index) {
	return DA->array[index];
}

// Inserez un element "x" in Array
void DA_Insert(DynamicArray DA, dynamic_array_element x) {
	// Verific daca s-a umplut Array-ul
	if(DA->size == DA->capacity) {
		DA->capacity <<= 1; // se dubleaza capacitatea Array-ului (complexitate mai buna fata de un += 100)
		DA->array = (dynamic_array_element*) realloc(DA->array, DA->capacity * sizeof(dynamic_array_element));
	}
	
	// Inserez elementul cu grija
	DA->array[DA->size] = x;
	DA->size++;
}

// Inversez un Array Dinamic
void DA_Reverse(DynamicArray DA) {
	dynamic_array_element swap;
	int i, size;
	
	size = DA->size;
	
	for(i = 0; i < (size >> 1); i++) {
		// Interschimb elementele simetrice fata de mijlocul vectorului
		swap = DA->array[i];
		DA->array[i] = DA->array[size-1-i] ;
		DA->array[size-1-i] = swap;
	}
}

#define INFINITY 12345

int BFS(DynamicArray *neighbour_lists, int n,
			int **capacity, int **flow, int *parent,
			int source, int sink) {
	int *path_capacity, *queue;
	int residual_capacity;
	int i, u, v, p, q;
	
	for(u = 0; u < n; u++)
		parent[u] = -1;
	parent[source] = -2;
	
	path_capacity = (int*) malloc(n * sizeof(int));
	path_capacity[source] = INFINITY;
	
	queue = (int*) malloc(n * sizeof(int));
	queue[0] = source;
	p = 0;
	q = 1;
	
	while(p < q) {
		u = queue[p++];
		
		for(i = 0; i < DA_Size(neighbour_lists[u]); i++) {
			v = DA_Get(neighbour_lists[u], i);
			
			if((capacity[u][v] > flow[u][v]) && (parent[v] == -1)) {
				parent[v] = u;
				residual_capacity = capacity[u][v] - flow[u][v];
				
				if(path_capacity[u] < residual_capacity)
					path_capacity[v] = path_capacity[u];
				else
					path_capacity[v] = residual_capacity;
				
				if(v == sink) {
					return path_capacity[v];
				} else {
					queue[q++] = v;
				}
			}
		}
	}
	
	return 0;
}

void EdmondsKarp(DynamicArray *neighbour_lists, int n,
			int **capacity,
			int source, int sink) {
	int **flow;
	int *parent;
	int max_flow, saturate;
	int i, u, v;
	
	flow = (int**) malloc(n * sizeof(int*));
	for(i = 0; i < n; i++)
		flow[i] = (int*) calloc(n, sizeof(int));
	
	parent = (int*) malloc(n * sizeof(int));
	
	max_flow = 0;
	
	for(;;) {
		saturate = BFS(neighbour_lists, n, capacity, flow, parent, source, sink);
		
		if(saturate == 0)
			break;
		
		max_flow += saturate;
		
		v = sink;
		
		while(v != source) {
			u = parent[v];
			
			flow[u][v] += saturate;
			flow[v][u] -= saturate;
			
			v = u;
		}
	}
	
	FILE *f = fopen("maxflow.out", "wt");
	
	fprintf(f, "%d\n", max_flow);
	
	fclose(f);
	
	for(u = 0; u < n - 2; u++)
		for(i = 0; i < DA_Size(neighbour_lists[u]); i++) {
			v = DA_Get(neighbour_lists[u], i);
			if((v < n - 2) && (flow[u][v] != 0))
				printf("%d %d %d\n", u + 1, v + 1, flow[u][v]);
		}
}

int main() {
	FILE *f;
	DynamicArray * neighbour_lists;
	int **capacity, **cost;
	int n, m;
	int source, sink;
	int u, v;
	int i, j;
	
	f = fopen("maxflow.in", "rt");
	
	if(f == NULL) {
		fprintf(stderr, "Fiserul retea.in n-a putut fi deschis.\n");
		exit(-1);
	}
	
	fscanf(f, "%d", &n);
	fscanf(f, "%d", &m);
	
	capacity = (int**) malloc((n + 2) * sizeof(int*));
	for(i = 0; i < n + 2; i++)
		capacity[i] = (int*) calloc(n + 2, sizeof(int));
	
	cost = (int**) malloc((n + 2) * sizeof(int*));
	for(i = 0; i < n + 2; i++)
		cost[i] = (int*) calloc(n + 2, sizeof(int));
	
	neighbour_lists = (DynamicArray*) malloc((n + 2) * sizeof(DynamicArray));
	for(i = 0; i < n + 2; i++)
		neighbour_lists[i] = DA_New();
	
	for(i = 0; i < m; i++) {
		fscanf(f, "%d", &u);
		fscanf(f, "%d", &v);
		
		u--;
		v--;
		
		DA_Insert(neighbour_lists[u], v);
		// ?
		
		fscanf(f, "%d", &capacity[u][v]);
		//fscanf(f, "%d", &cost[u][v]);
	}
	
	/*source = n;
	sink = n + 1;
	
	for(i = 0; i < n; i++) {
		fscanf(f, "%d", &u);
		
		if(u > 0) {
			DA_Insert(neighbour_lists[source], i);
			// ?
			capacity[source][i] = u;
		} else if(u < 0) {
			DA_Insert(neighbour_lists[i], sink);
			// ?
			capacity[i][sink] = -u;
		}
	}*/
	
	source = 0;
	sink = n - 1;
	
	#ifdef DEBUG
		
		for(i = 0; i < n + 2; i++) {
			fprintf(stderr, "debug: neighbour list for vertex %d\n", i);
			fprintf(stderr, "[ ");
			for(j = 0; j < DA_Size(neighbour_lists[i]); j++)
				fprintf(stderr, "%d ", DA_Get(neighbour_lists[i], j));
			fprintf(stderr, "]\n");
		}
		
		fprintf(stderr, "debug: capacity matrix\n");
		
		for(i = 0; i < n + 2; i++) {
			fprintf(stderr, "| ");
			for(j = 0; j < n + 2; j++)
				fprintf(stderr, "%d ", capacity[i][j]);
			fprintf(stderr, "|\n");
		}
		
		fprintf(stderr, "debug: cost matrix\n");
		
		for(i = 0; i < n + 2; i++) {
			fprintf(stderr, "| ");
			for(j = 0; j < n + 2; j++)
				fprintf(stderr, "%d ", cost[i][j]);
			fprintf(stderr, "|\n");
		}
		
	#endif
	
	EdmondsKarp(neighbour_lists, n, capacity, source, sink);
	
	// Ies de tot
	return 0;
}