#include <bits/stdc++.h>
using namespace std;
ifstream fin("maxflow.in");
ofstream fout("maxflow.out");

int graph[50][50],n,m,x,y,capacity,visited[50],flux_maxim=0;

void Read() {
    fin >> n >> m;
    for(int i = 1; i <= m; i++) {
        fin >> x >> y >> capacity;
        graph[x][y] = capacity;
    }
}

//input  : int : nod : nodul curent (in apel nod_source)
//output : return : 1 - a gasit un path de crestere
//                    - scoate prin parent drumul de crestere
//         return : 0 - nu a gasit path de crestere
int DFS(int nod,int parent[]) {
    visited[nod] = 1;
    for(int neighbour = 1; neighbour <= n; neighbour++)
        if(graph[nod][neighbour] > 0 && !visited[neighbour]) {//daca e nod nevizitat
            parent[neighbour] = nod;
            DFS(neighbour,parent);
        }
    if(visited[n] == 1)//daca e egal cu nodul de final , in cazul meu N
        return 1;//inseamna ca a gasit un drum de crestere
    else return 0;
}

//minimul flux de pe path-ul definit de parent[]
int min_FluxPath(int parent[]) {
    int minim = INT_MAX;
    for(int node = n; node != 1; node = parent[node]) {
        int right = node;
        int left = parent[node];

        if(graph[left][right] < minim)//daca pe ce a mai ramas din capacitate mai putem pompa flux
            minim = graph[left][right];
    }
    return minim;
}

void Fulkerson() {
    int *parent = new int[n+1];
    memset(parent,0,sizeof(parent));
    //luam un path
    while(DFS(1,parent)) { //cat timp am un drum de crestere
        int flux = min_FluxPath(parent);
        flux_maxim += flux;
        //for(int node = n; node != 1; node = parent[node]) {
        //    cout << node << " ";
        //}
        //cout << "1 \n";
        //mergem pe path
        for(int node = n; node != 1; node = parent[node]) {
            int right = node;
            int left = parent[node];
            graph[left][right] -= flux;//scad capacitatea pentru ca nu vreau sa iau acelasi path
            graph[right][left] += flux;//de incrementarea asta nu prea e nevoie in momentul de fata .
        }
        //resetez parent si visited pentru a genera urmatorul path
        memset(parent,0,sizeof(parent));
        memset(visited,0,sizeof(visited));
    }
}

int main() {
    Read();
    Fulkerson();
    fout << "Fluxul maxim este : " << flux_maxim;
    return 0;
}