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

#include "dynamic_trees/dynamic_trees.h"

#define INP_FILE stdin
#define OUT_FILE stdout

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;
    TDGEdge *in_edges;
} DGraph, *TDGraph;

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;

    return;
}

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) {
            make_and_add_edges(res_graph, i, iter->id, iter->cost - iter->flow);
            make_and_add_edges(res_graph, iter->id, i, iter->flow);

            iter = iter->next;
        }
    }

    return;
}

int make_level_graph_edges(TDGraph res_graph, TDGraph level_graph)
{
    int V = res_graph->V;
    int *levels = (int *) calloc(V, sizeof(int));
    int *visited = (int *) calloc(V, sizeof(int));

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

    enqueue(queue, 0);

    int current_vertex;

    while (queue->head != NULL) {
        current_vertex = dequeue(queue);
        TDGEdge iter = res_graph->out_edges[current_vertex];
        while (iter != NULL) {
            if ((levels[iter->id] != 0 && iter->id != V - 1 && levels[iter->id] <= levels[current_vertex]) ||
                    iter->cost <= 1e-9 || iter->id == 0) {
                iter = iter->next;
                continue;
            }

            make_and_add_edges(level_graph, current_vertex, iter->id, iter->cost);
            TDGEdge edge_in = (TDGEdge) calloc(1, sizeof(*edge_in));

            edge_in->id = current_vertex;
            edge_in->cost = iter->cost;
            edge_in->flow = 0;

            edge_in->next = level_graph->in_edges[iter->id];
            level_graph->in_edges[iter->id] = edge_in;
            
            levels[iter->id] = levels[current_vertex] + 1;
            if (visited[iter->id] == 0) {
                enqueue(queue, iter->id);
            }
            visited[iter->id] = 1;

            iter = iter->next;
        }
    }

    if (levels[V - 1] == 0) {
        return 0;
    }

    return 1;
}

void remove_out_edge_graph(TDGraph graph, int v1, int v2)
{
    TDGEdge iter = graph->out_edges[v1];
    TDGEdge parent = NULL;
    while (iter != NULL) {
        if (iter->id == v2) {
            if (parent == NULL) {
                graph->out_edges[v1] = iter->next;
            } else {
                parent->next = iter->next;
            }
            free(iter);

            return;
        }

        parent = iter;
        iter = iter->next;
    }

    return;
}

void remove_in_edge_graph(TDGraph graph, int v1, int v2)
{
    TDGEdge iter = graph->in_edges[v2];
    TDGEdge parent = NULL;
    while (iter != NULL) {
        if (iter->id == v2) {
            if (parent == NULL) {
                graph->in_edges[v2] = iter->next;
            } else {
                parent->next = iter->next;
            }
            free(iter);

            return;
        }

        parent = iter;
        iter = iter->next;
    }

    return;
}

void update_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;
    }

    return;
}

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

        iter = iter->next;
    }

    return;
}

void update_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;
    }
}

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

        iter = iter->next;
    }
    iter = graph->out_edges[v2];
    while (iter != NULL) {
        if (iter->id == v1) {
            capacity = iter->cost;
            iter->flow = res_cap;
        }

        iter = iter->next;
    }

    iter = res_graph->out_edges[v1];
    while (iter != NULL) {
        if (iter->id == v2) {
            iter->cost = res_cap;
        }

        iter = iter->next;
    }
    iter = res_graph->out_edges[v2];
    while (iter != NULL) {
        if (iter->id == v1) {
            iter->cost = capacity - res_cap;
        }

        iter = iter->next;
    }

    return;
}

void dfs_until_bf_and_modify_graphs(TDGraph graph, TDGraph res_graph, TDGraph level_graph, TDTree forest)
{
    int V = level_graph->V;
    while (1) {
        BBTree_Node *v = root(forest->vertices[0]);
        if (v->value == V - 1) {
            v = mincost(forest->vertices[0]);
            double c = cost(v);
            update(forest->vertices[0], -c);
            while (cost(v) == 0) {
                BBTree_Node *w = parent(v);
                update_res(res_graph, v->value, w->value, c);
                update_flow(graph, v->value, w->value, c);
                remove_out_edge_graph(level_graph, v->value, w->value);
                remove_in_edge_graph(level_graph, v->value, w->value);

                cut(v);

                if (parent(forest->vertices[0]) == NULL) {
                    break;
                }
                v = mincost(forest->vertices[0]);
            }
        } else {
            if (level_graph->out_edges[v->value] == NULL) {
                if (v == forest->vertices[0]) {
                    return;
                } else {
                    TDGEdge iter = level_graph->in_edges[v->value];
                    while (iter != NULL) {
                        double c;
                        TDGEdge aux = iter->next;
                        remove_out_edge_graph(level_graph, iter->id, v->value);
                        BBTree_Node *w = parent(forest->vertices[iter->id]);
                        c = cost(forest->vertices[iter->id]);
                        update_both(graph, res_graph, iter->id, v->value, c);
                        if (w == v) {
                            cut(forest->vertices[iter->id]);
                        }

                        remove_in_edge_graph(level_graph, iter->id, v->value);
                        iter = aux;
                    }
                }
            } else {
                link(v, forest->vertices[level_graph->out_edges[v->value]->id], level_graph->out_edges[v->value]->cost);
            }
        }
    }
}

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;
        }
        while (iter != NULL) {
            aux = iter->next;
            free(iter);
            iter = aux;
        }
    }
    free(graph->out_edges);
    free(graph->in_edges);
    free(graph);

    return;
}

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

    return;
}

double dinic_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);

    TDGraph level_graph = (TDGraph) malloc(sizeof(*level_graph));
    level_graph->V = graph->V;
    level_graph->out_edges = (TDGEdge *) calloc(res_graph->V, sizeof(TDGEdge));
    level_graph->in_edges = (TDGEdge *) calloc(res_graph->V, sizeof(TDGEdge));
    level_graph->E = 0;

    TDTree forest = init_trees(graph->V);

    int there_is_path = make_level_graph_edges(res_graph, level_graph);
    while (there_is_path == 1) {
        dfs_until_bf_and_modify_graphs(graph, res_graph, level_graph, forest);
        for (int i = 0; i < graph->V; i++) {
            free_path_without_leaves(forest->vertices[i]);
            forest->vertices[i]->dparent = NULL;
        }
        
        free_edges(level_graph);
        there_is_path = make_level_graph_edges(res_graph, level_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));

    int v1, v2;
    double cost;
    for (int i = 0; i < graph->E; i++) {
        fscanf(INP_FILE, "%d%d%lf", &v1, &v2, &cost);
        v1--;
        v2--;
        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 = dinic_max_flow(graph);
    fprintf(OUT_FILE, "%d\n", max_flow);
    free_graph(graph);

    return 0;
}