#include <iostream>
#include <fstream>
#include <vector>
#define DIM 1005
#define s 1


class edge{
public:
    int u,v,flow,cap;
    edge(int u, int v, int flow, int cap):u{u},v{v},flow{flow},cap{cap}{}
};

class vertex{
public:
    int e,h;
    vertex()= default;
    vertex(int e, int h):e{e},h{h}{}
};

std::vector<edge> E,Ef;
vertex V[DIM];
int n,m,t;

int find(int u, int v, std::vector<edge>& E){
    for(int i=0;i<E.size();i++){
        if(E[i].u==u&&E[i].v==v) return i;
    }
    return -1;
}

void read(){
    std::ifstream f("maxflow.in");
    f>>n>>m;
    t=n;
    for(int i=0;i<m;i++){
        int u,v,cap;
        f>>u>>v>>cap;
        if(-1 != find(v, u, E)){
            n++;
            E.push_back(edge(u,n,0,cap));
            E.push_back(edge(n,v,0,cap));
        }
        else
            E.push_back(edge(u,v,0,cap));
    }
    Ef=E;
    f.close();
}


void reverseEdge(int u, int v, int flow){
    for(auto &e:Ef){
        if(e.u==v&&e.v==u){
            e.flow-=flow;
            return;
        }
    }
    Ef.push_back(edge(v,u,0,flow));
}

void pump(int u, int v){
    int e=find(u,v,Ef);
    int quantity;
    if(Ef[e].cap-Ef[e].flow<V[u].e) quantity=Ef[e].cap-Ef[e].flow;
    else quantity=V[u].e;
    Ef[e].flow+=quantity;
    if(Ef[e].flow==Ef[e].cap) Ef.erase(Ef.begin()+e);
    reverseEdge(u,v,quantity);
    V[u].e-=quantity;
    V[v].e+=quantity;
}

void lift(int u){
    int min=30000;
    for(auto &e:Ef){
        if(e.u==u)
            if(V[e.v].h<min) min=V[e.v].h;
    }
    V[u].h=min+1;
}

void init(){
    for(int i=1;i<=n;i++){
        V[i].h=0;
        V[i].e=0;
    }
    V[s].h=n+1;
    std::vector<int> v;
    for(int i=0;i<Ef.size();i++){
        if(Ef[i].u==s){
            V[s].e-=Ef[i].cap;
            V[Ef[i].v].e+=Ef[i].cap;
            reverseEdge(Ef[i].u,Ef[i].v,Ef[i].cap);
            Ef.erase(Ef.begin()+i);
            i--;
        }
    }
}

bool cond_p(int u, int v){
    if(u==s||u==t) return false;
    if(V[u].e<=0) return false;
    int e=find(u,v,Ef);
    if(Ef[e].cap-Ef[e].flow<=0) return false;
    return V[u].h == V[v].h + 1;
}

bool cond_l(int u){
    if(u==s||u==t) return false;
    if(V[u].e<=0) return false;
    for(auto &e:Ef){
        if(e.u==u&&V[u].h>V[e.v].h) return false;
    }
    return true;
}


void preflow_push(){
    init();
    bool go=true;
    while (go){
        go = false;
        for(auto &e:Ef){
            if(cond_p(e.u,e.v)){
                pump(e.u,e.v);
                go= true;
                break;
            }
        }
        if(!go){
            for(int u=1;u<=n;u++){
                if(cond_l(u)){
                    lift(u);
                    go= true;
                    break;
                }
            }
        }
    }
}

void print(){
    std::ofstream f("maxflow.out");
    f<<V[t].e;
    f.close();
}

int main() {
    read();
    preflow_push();
    print();
    return 0;
}