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

#define INP_FILE in_file
#define OUT_FILE out_file

typedef struct queue_cell {
    int value;
    struct queue_cell *next;
} QCell, *TQCell;

typedef struct squeue {
    TQCell head;
    TQCell tail;
} Queue, *TQueue;

void enqueue(TQueue queue, int val)
{
    TQCell cell = (TQCell) malloc(sizeof(*cell));
    cell->value = val;
    cell->next = NULL;
    if (queue->head == NULL) {
        queue->head = cell;
        queue->tail = cell;

        return;
    }

    queue->tail->next = cell;
    queue->tail = cell;

    return;
}

int dequeue(TQueue queue)
{
    int value = queue->head->value;

    if (queue->head == queue->tail) {
        free(queue->head);
        queue->head = queue->tail = NULL;

        return value;
    }

    TQCell aux = queue->head;
    queue->head = queue->head->next;
    free(aux);

    return value;
}

void destroy_queue(TQueue queue)
{
    while (queue->head != NULL) {
        dequeue(queue);
    }
    free(queue);

    return;
}

typedef struct dgraph_edge {
    int id;
    double cost;
    double flow;
    struct dgraph_edge *next;
} DGEdge, *TDGEdge;

typedef struct dgraph {
    int V, E;
    TDGEdge *out_edges;
} DGraph, *TDGraph;

int are_same_double(double a, double b) 
{
    if (fabs(a - b) < 1e-9) {
        return 1;
    }

    return 0;
}

void make_and_add_edges(TDGraph graph, int v1, int v2, double cost)
{
    TDGEdge edge_out = (TDGEdge) calloc(1, sizeof(*edge_out));

    edge_out->id = v2;
    edge_out->cost = cost;
    edge_out->flow = 0;

    edge_out->next = graph->out_edges[v1];
    graph->out_edges[v1] = edge_out;
}

void make_res_graph_edges(TDGraph graph, TDGraph res_graph)
{
    for (int i = 0; i < graph->V; i++) {
        TDGEdge iter = graph->out_edges[i];
        while (iter != NULL) {
            TDGEdge edge_out1 = (TDGEdge) calloc(1, sizeof(*edge_out1));
            TDGEdge edge_out2 = (TDGEdge) calloc(1, sizeof(*edge_out2));

            edge_out1->id = iter->id;
            edge_out2->id = i;

            edge_out1->cost = iter->cost - iter->flow;
            edge_out2->cost = iter->flow;

            edge_out1->next = res_graph->out_edges[i];
            res_graph->out_edges[i] = edge_out1;

            edge_out2->next = graph->out_edges[iter->id];
            graph->out_edges[iter->id] = edge_out2;

            iter = iter->next;
        }
    }
}

void change_edge_flow(TDGraph graph, int v1, int v2, double flow)
{
    TDGEdge iter = graph->out_edges[v1];
    while (iter != NULL) {
        if (iter->id == v2) {
            iter->flow += flow;
            return;
        }

        iter = iter->next;
    }

    iter = graph->out_edges[v2];

    while (iter != NULL) {
        if (iter->id == v1) {
            iter->flow -= flow;
            return;
        }

        iter = iter->next;
    }
}

void change_edge_res(TDGraph res_graph, int v1, int v2, double flow)
{
    TDGEdge iter = res_graph->out_edges[v1];
    while (iter != NULL) {
        if (iter->id == v2) {
            iter->cost -= flow;
            break;
        }

        iter = iter->next;
    }

    iter = res_graph->out_edges[v2];

    while (iter != NULL) {
        if (iter->id == v1) {
            iter->cost += flow;
            return;
        }

        iter = iter->next;
    }
}

int bfs_and_modify_graphs(TDGraph graph, TDGraph res_graph)
{
    int V = graph->V;
    int *parents = (int *) malloc(V * sizeof(int));
    int *visited = (int *) calloc(V, sizeof(int));
    double *costs_to_parents = (double *) malloc(V * sizeof(double));

    TQueue queue = (TQueue) malloc(sizeof(*queue));
    queue->head = queue->tail = NULL;

    enqueue(queue, 0);
    visited[0] = 1;
    parents[0] = -1;

    int current_vertex;
    
    int found_path = 0;
    while (queue->head != NULL) {
        current_vertex = dequeue(queue);
        TDGEdge iter = res_graph->out_edges[current_vertex];
        while (iter != NULL) {
            if (visited[iter->id] == 0 && iter->cost > 0) {
                parents[iter->id] = current_vertex;
                visited[iter->id] = 1;
                costs_to_parents[iter->id] = iter->cost;

                if (iter->id == V - 1) {
                    found_path = 1;
                    break;
                }
                enqueue(queue, iter->id);
            }

            iter = iter->next;
        }
        if (found_path == 1) {
            break;
        }
    }

    if (found_path == 0) {
        free(parents);
        free(visited);
        free(costs_to_parents);
        destroy_queue(queue);

        return 0;
    }

    double critical_cost = (int)0x7fffffff;
    int last = V - 1;
    while (last != 0) {
        if (costs_to_parents[last] < critical_cost) {
            critical_cost = costs_to_parents[last];
        }
        last = parents[last];
    }


    current_vertex = V - 1;
    int current_parent = parents[current_vertex];
    while (parents[current_vertex] != -1) {
        change_edge_flow(graph, current_parent, current_vertex, critical_cost);
        change_edge_res(res_graph, current_parent, current_vertex, 
                critical_cost);
        current_vertex = current_parent;
        current_parent = parents[current_vertex];
    }

    free(parents);
    free(visited);
    free(costs_to_parents);
    destroy_queue(queue);

    return 1;

}

void free_graph(TDGraph graph)
{
    int V = graph->V;
    for (int i = 0; i < V; i++) {
        TDGEdge iter = graph->out_edges[i];
        TDGEdge aux;
        while (iter != NULL) {
            aux = iter->next;
            free(iter);
            iter = aux;
        }
    }
    free(graph->out_edges);
    free(graph);

    return;
}

double edmonds_karp_max_flow(TDGraph graph)
{
    TDGraph res_graph = (TDGraph) malloc(sizeof(*res_graph));
    res_graph->V = graph->V;
    res_graph->E = 2 * graph->E;
    res_graph->out_edges = (TDGEdge *) calloc(res_graph->V, sizeof(TDGEdge));
   
    make_res_graph_edges(graph, res_graph);
    int there_is_path = 1;
    while (there_is_path == 1) {
        there_is_path = bfs_and_modify_graphs(graph, res_graph);
    }

    double flow = 0;
    TDGEdge iter = graph->out_edges[0];
    while (iter != NULL) {
        flow += iter->flow;
        iter = iter->next;
    }

    free_graph(res_graph);

    return flow;
}

int main( int argc, const char* args[] )
{
    TDGraph graph = (TDGraph) malloc(sizeof(*graph));
    fscanf(INP_FILE, "%d%d", &graph->V, &graph->E);
    graph->out_edges = (TDGEdge *) calloc(graph->V, sizeof(TDGEdge));
    FILE *in_file = fopen("maxflow.in", "r");
    FILE *out_file = fopen("maxflow.out", "w");
    int v1, v2;
    double cost;
    for (int i = 0; i < graph->E; i++) {
        fscanf(INP_FILE, "%d%d%lf", &v1, &v2, &cost);
        if (v2 == 0 || v1 == graph->V - 1) {
            printf("Vertex giving to source or taking from sink.\n");
            return 1;
        }
        make_and_add_edges(graph, v1, v2, cost);
    }
    double max_flow = edmonds_karp_max_flow(graph);
    fprintf(OUT_FILE, "%lf\n", max_flow);
    free_graph(graph);

    return 0;
}