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

using std::cout;


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}{}
    ~edge()= default;
};

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

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

class Node{
public:
    int u;
    Node* next= nullptr;
    Node(int u):u{u}{}
};


Node* N[DIM];
Node* current[DIM];

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 add_N(int u, int v, Node* N[]){
    Node* n=new Node(v);
    if(N[u]== nullptr){
        N[u]=n;
    }
    else {
        auto current=N[u];
        while (current->next != nullptr) current = current->next;
        current->next = n;
    }
}

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));
            add_N(u,n,N);
            add_N(n,u,N);
            add_N(n,v,N);
            add_N(v,n,N);
        }
        else {
            E.push_back(edge(u, v, 0, cap));
            add_N(u,v,N);
            add_N(v,u,N);
        }
    }
    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 print_graph(){
    cout<<"Graph is:\n";
    for(auto &e:Ef)
        cout<<e.u<<"-"<<e.v<<": cap "<<e.cap<<", flow "<<e.flow<<"\n";
    cout<<"\n";
    for(int i=0;i<n;i++) cout<<i<<":"<<V[i].h<<" ";
    cout<<"\n";
    for(int i=0;i<n;i++) cout<<i<<":"<<V[i].e<<" ";
    cout<<"\n\n";
}


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

void make_top(int u, std::deque<int>& L){
    for(int i=0;i<L.size();i++)
        if(L[i]==u){
            L.erase(L.begin()+i);
            break;
        }
    L.push_front(u);
}

void unload(int u){
    while(V[u].e>0){
        auto v=current[u];
        if(v== nullptr){
            lift(u);
            current[u]=N[u];

        }
        else {
            auto e=find(u,v->u,Ef);
            if((e!=-1)&&(V[u].h==V[v->u].h+1)&&(Ef[e].cap-Ef[e].flow>0)){
                pump(u,v->u);
            }
            else {
                current[u] = v->next;
            }
        }
    }
}





void relabel_to_front(){
    init();
    std::deque<int> L;
    for(int u=0;u<n;u++){
        if(u!=s&&u!=t) {
            L.push_back(u);
            current[u]=N[u];
        }
    }
    auto u=L.begin();
    while(u!=L.end()){
        int old_h=V[*u].h;
        unload(*u);
        if(V[*u].h>old_h) {
            make_top(*u, L);
            u = L.begin() + 1;
        }
        else
            u++;
    }
}

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

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