#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;

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

    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 && levels[iter->id] <= levels[current_vertex]) ||
                    iter->cost <= 0 || iter->id == 0) {
                iter = iter->next;
                continue;
            }

            make_and_add_edges(level_graph, current_vertex, iter->id, iter->cost);
            levels[iter->id] = levels[current_vertex] + 1;
            enqueue(queue, iter->id);

            iter = iter->next;
        }
    }

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

    return 1;

}

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 dfs_once_level_graph(int *parents, double *costs_to_parents, TDGraph level_graph, int vertex)
{
    if (parents[level_graph->V - 1] != -1) {
        return;
    }

    TDGEdge iter = level_graph->out_edges[vertex];
    while (iter != NULL) {
        if (iter->cost <= 0) {
            iter = iter->next;
            continue;
        }
        parents[iter->id] = vertex;
        costs_to_parents[iter->id] = iter->cost;

        dfs_once_level_graph(parents, costs_to_parents, level_graph, iter->id);

        iter = iter->next;
    }

    return;
}

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

    parents[0] = -1;
    parents[V - 1] = -1;

    dfs_once_level_graph(parents, costs_to_parents, level_graph, 0);
    
    while (parents[V - 1] != -1) {
        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];
        }

        int current_vertex = V - 1;
        int current_parent = parents[current_vertex];
        while (parents[current_vertex] != -1) {
            update_flow(graph, current_parent, current_vertex, critical_cost);
            update_res(res_graph, current_parent, current_vertex, critical_cost);
            update_cost_level_graph(level_graph, current_parent, current_vertex, critical_cost);
            current_vertex = current_parent;
            current_parent = parents[current_vertex];
        }


        for (int i = 1; i < V; i++) {
            parents[i] = 0;
        }

        parents[V - 1] = -1;

        dfs_once_level_graph(parents, costs_to_parents, level_graph, 0);
    }

    return;
}

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

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;
        }
    }
    for (int i = 0; i < V; i++) {
        level_graph->out_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->E = 0;

    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);
        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));
    FILE *in_file = fopen("maxflow.in", "r");
    FILE *out_file = fopen("maxflow.out", "w");
    
    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", (int)max_flow);
    free_graph(graph);

    return 0;
}