#include <iostream>
#include <cstdio>
#include <queue>
#include <vector>
using namespace std;
queue<int> Q;
int Flow[1001][1001], i, N, M, j, Graph[1001][1001], Past[1001], Count[1001];
int long long Solution, Cap;
bool BFS();
int DFS(int i, int long long val);
int main()
{
    freopen("maxflow.in", "r", stdin);
    freopen("maxflow.out", "w", stdout);
    scanf("%d%d", &N, &M);
    for(i=1; i<=M; ++i){
        int x, y, z;
        scanf("%d%d%d", &x, &y, &z);
        Flow[x][y]+=z;
        if(x==1) Cap+=z;
    }
    while(true){
        if(BFS()==false) break;
        Solution+=DFS(1, Cap-Solution);
    }
    printf("%lld", Solution);
    return 0;
}
bool BFS(){
    bool out=false;
    int i, j;
    for(j=1; j<=N; ++j){Graph[j][0]=0; Past[j]=Count[j]=0;}
    Q.push(1); Count[1]=1;
    while(!Q.empty()){
        i=Q.front(); Q.pop();
        if(i==N){out=true; break;}
        for(j=1; j<=N; ++j){
            if(Flow[i][j]==0) continue;
            if(Count[j]==0){
                Count[j]=Count[i]+1;
                Graph[i][++Graph[i][0]]=j;
                Q.push(j);
            }
            else if(Count[j]==Count[i]+1) Graph[i][++Graph[i][0]]=j;
        }
    }
    while(!Q.empty()) Q.pop();
    return out;
}
int DFS(int i, int long long val){
    int out=0;
    int j;
    if(val==0) return 0;
    if(i==N) return val;
    for(j=1; j<=Graph[i][0]; ++j){
        int x=Graph[i][j];
        if(Flow[i][x]==0) continue;
        int r=DFS(x, min(int(val-out), Flow[i][x]));
        if(r!=0){
            Flow[i][x]-=r;
            Flow[x][i]+=r;
            out+=r;
        }
    }
    return out;
}