#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#define DIM 1005

class adj_node{
public:
    int y,cap;
    adj_node(int y, int cap):y{y},cap{cap}{}
};

class Node{
public:
    int e,h;
};

std::vector<adj_node> G[DIM],Gf[DIM];
int n,m,dest,source=1;
Node node[DIM];

void read(){
    std::ifstream f("maxflow.in");
    f>>n>>m;
    dest=n;
    for(int i=0;i<m;i++){
        int x,y,cap;
        f>>x>>y>>cap;
        bool found=false;
        for(auto node:G[y]) {
            if (node.y == x) {
                found = true;
                break;
            }
        }
        if(found) {
            n++;
            G[x].push_back(adj_node(n, cap));
            G[n].push_back(adj_node(y, cap));
        }
        else
            G[x].push_back(adj_node(y, cap));

    }
    for(int i=1;i<=n;i++){
        Gf[i]=G[i];
    }
    f.close();
}

void printGraph(std::vector<adj_node> G[]){
    for(int i=1;i<=n;i++){
        std::cout<<i<<": ";
        for(auto v:G[i])
            std::cout<<"|"<<v.y<<" "<<v.cap<<"| ";
        std::cout<<"\n";
    }
    std::cout<<"\n";
}
void pump(int u, int v){
    int quantity=node[u].e;
    for(auto v1:G[u]){
        if(v1.y==v){
            if(v1.cap<quantity) quantity=v1.cap;
            break;
        }
    }
    bool found=false;
    for(int i=0;i<G[u].size();i++) {
        if (G[u][i].y == v) {
            found = true;
            break;
        }
    }
    if(found) {
        for (int i = 0; i < Gf[u].size(); i++) {
            if (Gf[u][i].y == v) {
                Gf[u][i].cap -= quantity;
                if (Gf[u][i].cap == 0) {
                    Gf[u].erase(Gf[u].begin() + i);
                }
                bool found1 = false;
                for (int j = 0; j < Gf[v].size(); j++)
                    if (Gf[v][j].y == u) {
                        found1 = true;
                        Gf[v][j].cap += quantity;
                        break;
                    }
                if (!found1) {
                    Gf[v].push_back(adj_node(u, quantity));
                }
                break;
            }
        }
    }
    else{
        for(int i=0;i<Gf[v].size();i++){
            if(Gf[v][i].y==u)
                Gf[v][i].cap-=quantity;
        }
    }
    node[u].e-=quantity;
    node[v].e+=quantity;
}

void lift(int u){
    int min=n+2;
    for(auto v:Gf[u]){
        if(node[v.y].h<min)
            min=node[v.y].h;
    }
    node[u].h=min+1;
}

void init(int s){
    for(int i=1;i<=n;i++){
        node[i].e=0;
        node[i].h=0;
    }
    node[s].h=n+1;
    node[s].e=100000;
    for(auto v:G[s]){
        pump(s,v.y);
    }
}

bool cond_pump(int u, int v){
    if(u==source||u==dest) return false;
    if(node[u].e==0) return false;
    if(node[u].h!=node[v].h+1) return false;
    return true;
}

bool cond_lift(int u){
    if(u==source||u==dest) return false;
    if(node[u].e==0) return false;
    for(auto v:Gf[u]){
        if(node[u].h>node[v.y].h) return false;
    }
    return true;
}

void PreflowPush(){
    init(source);
    bool go=true;
    while(go){
        go=false;
        for(int u=1;u<=n;u++){
            for(auto v:Gf[u]){
                if(cond_pump(u,v.y)){
                    pump(u,v.y);
                    go=true;
                    break;
                }
            }
            if(go) break;
        }
        if(!go){
            for(int u=1;u<=n;u++){
                if(cond_lift(u)){
                    lift(u);
                    go=true;
                    break;
                }
            }
        }
    }
}

void print(){
    std::ofstream f("maxflow.out");
    f<<node[dest].e;
    f.close();
}
int main() {
    read();
    PreflowPush();
    print();
    return 0;
}