#include <bits/stdc++.h>
#define NMAX 1002
#define INF INT_MAX

using namespace std;

ifstream fin("maxflow.in");
ofstream fout("maxflow.out");

struct Vertex{
    int from;
    int to;
    int capacity;
    int flow;
    int next;
};

int N,M,a,b;
vector <Vertex> V;
int frst[NMAX];
char vizitat[NMAX];
int from[NMAX];
int ans;

bool can_travel(int curr)
{
    return V[curr].capacity-V[curr].flow>0 && !vizitat[V[curr].to];
}

bool dfs(int nod)
{
    if(nod==N){
        return 1;
    }
//    cout << nod << "!" << endl;
    int curr=frst[nod];
    vizitat[nod]=1;
    while(curr>=0){
        if(can_travel(curr)){
            from[V[curr].to]=curr;
            if(dfs(V[curr].to)){
                return 1;
            }
        }
        curr=V[curr].next;
    }
    return 0;
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    fin >> N >> M;
    for(int i=1;i<=N;i++){
        frst[i]=-1;
    }
    for(int i=1;i<=M;i++){
        int nc;
        fin >> a >> b >> nc;
        V.push_back({a,b,nc,0,frst[a]});
        frst[a]=int(V.size())-1;
        V.push_back({b,a,0,0,frst[b]});
//        frst[b]=int(V.size())-1;
    }
//    cout << V[0].next << "\n";
    ///max_flow
    while(dfs(1)){
//        cout << 2 << endl;
        int min_diff=INF;
        int curr=from[N];
        from[1]=-1;
        while(curr>=0){
            min_diff=min(min_diff,V[curr].capacity-V[curr].flow);
            curr=from[V[curr].from];
            cout << curr << "\n";
        }
        curr=from[N];
//        cout << min_diff << " * " << (min_diff!=INF) << "\n";
        ans+=min_diff*(min_diff!=INF);
        while(curr>=0){
            V[curr].flow+=min_diff;
            V[curr^1].flow-=min_diff;
            curr=from[V[curr].from];
//            cout << curr << "]\n";
        }
        memset(vizitat,0,sizeof(vizitat));
        for(int i=0;i<=N;i++){
            from[i]=-1;
        }
    }
    fout << ans << endl;
    return 0;
}