#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <algorithm>
#include <string>


//o clasa pentru flux speciala asa
//o clasa pentru grafuri normale desteapta
//asta o sa aiba sa faca apm
//sa faca si componentele tare conexe
//sa gaseasca cel mai scurt drum de la x la y, functioneaza dijkstra aici cred
//sa aiba si sortare topologica


using namespace std;

ifstream f("maxflow.in");
ofstream g("maxflow.out");

vector<vector<int>> graf;
vector<int> vizitat;
vector<int> tata;
vector<vector<int>> capacitate;
vector<vector<int>> flux;

int n, m, sursa, dest;

void bfs(){
    fill(vizitat.begin(), vizitat.end(), 0);
    queue<int> coada;
    coada.push(sursa);
    vizitat[sursa] = 1;

    while(!coada.empty()){
        int nod = coada.front();
        coada.pop();
        if(nod == dest)
            continue;
        for(auto &vecin:graf[nod]){
            if(capacitate[nod][vecin] == flux[nod][vecin] || vizitat[vecin] == 1)
                continue;
            vizitat[vecin] = 1;
            tata[vecin] = nod;
            coada.push(vecin);
        }
    }
}

int fluxMaxim(){
    int maxFlux = 0;
    bfs();
    cout<<"dupa bfs";
    while(vizitat[dest] == 1){
        for(auto vecin: graf[dest]){
            if(capacitate[vecin][dest] == flux[vecin][dest] || vizitat[vecin] == 0)
                continue;
            tata[dest] = vecin;

            int minim = capacitate[tata[dest]][dest] - flux[tata[dest]][dest];
            vecin = tata[dest];
            while(vecin != sursa){
                minim = min(capacitate[tata[vecin]][vecin] - flux[tata[vecin]][vecin], minim);
                vecin = tata[vecin];
            }

            vecin = dest;
            while(vecin != sursa){
                flux[tata[vecin]][vecin] += minim;
                flux[vecin][tata[vecin]] -= minim;
                vecin = tata[vecin];
            }

            maxFlux += minim;

        }
        bfs();
        cout<<"dupa alt bfs\n";
        cout<<maxFlux;
        cout<<"\n";
    }
    return maxFlux;
}

int main() {

    f>>n>>m;
    sursa = 1;
    dest = n;
    graf.resize(n+1);
    vizitat.resize(n+1);
    tata.resize(n+1);
    capacitate.resize(n+1, vector<int>(n+1));
    flux.resize(n+1, vector<int>(n+1));

    for(int i = 1; i <= m; i++){
        int x, y, c;
        f>>x>>y>>c;
        graf[x].push_back(y);
        graf[y].push_back(x);
        capacitate[x][y] = c;
    }

    //afisare matrice de capacitate
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= n; j++){
            cout<<capacitate[i][j]<<" ";
        }
        cout<<endl;
    }

    g<<fluxMaxim();

    return 0;
}