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

#define INP_FILE in_file
#define OUT_FILE out_file

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

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

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


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

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

    edge_in->id = v1;
    edge_in->is_out = 0;
    edge_in->cost = cost;
    edge_in->flow = 0;

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

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

    edge_in->next = graph->adj_arr[v2];
    graph->adj_arr[v2] = edge_in;

    return;
}

TGEdge out_edge(TDGraph graph, int v1, int v2)
{
    TGEdge iter = graph->adj_arr[v1];
    while (iter != NULL) {
        if (iter->id == v2 && iter->is_out == 1) {
            return iter;
        }

        iter = iter->next;
    }

    return NULL;
}

TGEdge in_edge(TDGraph graph, int v1, int v2)
{
    TGEdge iter = graph->adj_arr[v2];
    while (iter != NULL) {
        if (iter->id == v1 && iter->is_out == 0) {
            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 = out_edge(graph, v1, v2);
    TGEdge equiv_edge = in_edge(graph, v1, v2);
    double capacity, flow;

    int edge_exists = 1;
    if (edge == NULL) {
        edge = out_edge(graph, v2, v1);
        equiv_edge = in_edge(graph, v2, v1);
        edge_exists = 0;
    }
    capacity = edge->cost;
    flow = edge->flow;
    double res_cap = edge_exists ? capacity - flow : flow;

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

    if (edge_exists == 1) {
        edge->flow += df;
        equiv_edge->flow += df;
    } else {
        edge->flow -= df;
        equiv_edge->flow -= 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->adj_arr[v];
    while (iter != NULL) {
        if (graph->h[iter->id] < graph->h[v]) {
            double res_cap = iter->is_out == 1 ? iter->cost - iter->flow : iter->flow;
            if (res_cap < 1e-9) {
                iter = iter->next;
                continue;
            }
            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->adj_arr[u];
        } else {
            double res_cap;
            if (v->is_out == 1) {
                res_cap = v->cost - v->flow;
            } else {
                res_cap = v->flow;
            }
            if (res_cap > 0 && 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);

    while (graph->vertex_list != NULL) {
        TGVertex_lists aux = graph->vertex_list->next;
        free(graph->vertex_list);
        graph->vertex_list = aux;
    }

    TGEdge iter;
    for (int i = 0; i < graph->V; i++) {
        iter = graph->adj_arr[i];
        while (iter != NULL) {
            TGEdge aux = iter->next;
            free(iter);
            iter = aux;
        }
    }
    free(graph->adj_arr);
    free(graph->current_in_list);
    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->adj_arr = (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(graph, v1, v2, cost);
    }
    fclose(in_file);

    for (int i = 1; i < graph->V - 1; i++) {
        graph->current_in_list[i] = graph->adj_arr[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();

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

    free_graph(graph);

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

    return 0;
}