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

#define INP_FILE in_file
#define OUT_FILE out_file

typedef struct struct_edge {
    int id;
    double flow;
    double cost;
    struct struct_edge *next;
} GEdge, *TGEdge;

typedef struct struct_vertex_list {
    int vertex;
    struct struct_vertex_list *next;
} GVertex_lists, *TGVertex_lists;

typedef struct struct_dgraph {
    int V, E;
    TGVertex_lists vertex_list;
    TGEdge *out_edges;
    TGEdge *current_in_list;
    int *h;
    double *overflow;
} DGraph, *TDGraph;

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

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

    if (v1 == 0) {
        edge_out->flow = cost;
        graph->overflow[0] -= cost;
        graph->overflow[v2] = cost;
    }

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

    return;
}

void make_and_add_edges(TDGraph graph, int v1, int v2, double cost)
{
    TGEdge edge_out = (TGEdge) 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;
}

TDGraph make_res_graph(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 = (TGEdge *) calloc(res_graph->V, sizeof(TGEdge));
    res_graph->h = graph->h;
    res_graph->overflow = graph->overflow;
    res_graph->current_in_list = graph->current_in_list;
    res_graph->vertex_list = graph->vertex_list;
   
    for (int i = 0; i < graph->V; i++) {
        TGEdge 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 res_graph;
}

TGEdge find_edge(TDGraph graph, int v1, int v2)
{
    TGEdge iter = graph->out_edges[v1];
    while (iter != NULL) {
        if (iter->id == v2) {
            return iter;
        }

        iter = iter->next;
    }

    return NULL;
}

// Assumes v1 is overflowing, c_f(v1, v2) > 0 and h[v1] == h[v2] + 1.
void push(TDGraph graph, int v1, int v2) 
{
    TGEdge edge = find_edge(graph, v1, v2);
    TGEdge op_edge = find_edge(graph, v2, v1);
    
    double res_cap = edge->cost;

    double df = graph->overflow[v1] < res_cap ? graph->overflow[v1] : res_cap;

    edge->cost -= df;
    op_edge->cost += df;    

    graph->overflow[v1] -= df;
    graph->overflow[v2] += df;

    return;
}

// Assumes v is overflowing and h[v] <= h[u] for any adjacent node u.
void relabel(TDGraph graph, int v)
{
    graph->h[v] = 2 * graph->V;
    TGEdge iter = graph->out_edges[v];
    while (iter != NULL) {
        if (graph->h[iter->id] < graph->h[v] && iter->cost > 1e-9) {
            graph->h[v] = graph->h[iter->id];
        }

        iter = iter->next;
    }

    graph->h[v]++;

    return;
}

void discharge(TDGraph graph, int u)
{
    while (graph->overflow[u] > 1e-9) {
        TGEdge v = graph->current_in_list[u];
        if (v == NULL) {
            relabel(graph, u);
            graph->current_in_list[u] = graph->out_edges[u];
        } else {
            double res_cap = v->cost;
            if (res_cap > 1e-9 && graph->h[u] == graph->h[v->id] + 1) {
                push(graph, u, v->id);
            } else {
                graph->current_in_list[u] = v->next;
            }
        } 

    }
}

double RTF_PR(TDGraph graph)
{
    TGVertex_lists u = graph->vertex_list;
    TGVertex_lists parent = NULL;
    while (u != NULL) {
        int old_height = graph->h[u->vertex];
        discharge(graph, u->vertex);
        if (graph->h[u->vertex] > old_height) {
            if (parent != NULL) {
                parent->next = u->next;
                parent = NULL;
                u->next = graph->vertex_list;
                graph->vertex_list = u;
            }
        }

        parent = u;
        u = u->next;
    }



    return -graph->overflow[0];
}

void free_graph(TDGraph graph)
{
    free(graph->overflow);
    free(graph->h);

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

    return;
}

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

    return;
}

TDGraph read_graph()
{
    TDGraph graph = (TDGraph) malloc(sizeof(*graph));

    FILE *in_file = fopen("maxflow.in", "r");
    
    fscanf(INP_FILE, "%d%d", &graph->V, &graph->E);

    graph->h = (int *) calloc(graph->V, sizeof(int));
    
    graph->overflow = (double *) calloc(graph->V, sizeof(double));

    graph->h[0] = graph->V;

    graph->out_edges = (TGEdge *) calloc(graph->V, sizeof(TGEdge));

    graph->current_in_list = (TGEdge *) calloc(graph->V, sizeof(TGEdge));

    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 NULL;
        }
        make_and_add_edges_first(graph, v1, v2, cost);
    }
    fclose(in_file);

    for (int i = 1; i < graph->V - 1; i++) {
        graph->current_in_list[i] = graph->out_edges[i];
    }

    graph->vertex_list = (TGVertex_lists) malloc(sizeof(*graph->vertex_list));
    graph->vertex_list->vertex = 1;

    TGVertex_lists parent = graph->vertex_list;
    parent->next = NULL;

    TGVertex_lists new_list;
    for (int i = 2; i < graph->V - 1; i++) {
        new_list = (TGVertex_lists) malloc(sizeof(*new_list));
        new_list->next = NULL;
        new_list->vertex = i;
        parent->next = new_list;
        parent = new_list;
    }

    return graph;
}

int main( int argc, const char* args[] )
{
    TDGraph graph = read_graph();
    TDGraph res_graph = make_res_graph(graph);

    double max_flow;
    if (graph->V == 2) {
        max_flow = -graph->overflow[0];
    } else {
        max_flow = RTF_PR(res_graph);
    }

    free_graph(graph);
    free_res_graph(res_graph);

    FILE *out_file = fopen("maxflow.out", "w");
    fprintf(out_file, "%d\n", (int)fabs(max_flow));
    fclose(out_file);

    return 0;
}