//program 3.4 Flux maxim
#include <fstream>
#include <iostream>
#include <queue>
using namespace std;
int c[1001][1001], f[1001][1001];
int viz[1001],T[1001];
int n,m,lung,minim;
ifstream fin("maxflow.in");
ofstream fout("maxflow.out");
queue <int> fr;
void bf(){
 int i,j;
 queue <int> q;
 fill(viz,viz+1001,0);fill(T,T+1001,0);
 viz[n]=1;
 q.push(1);
 viz[1] = 1;
 while (q.empty() != 1){
    i = q.front();
//    if (i == n)return 1;
    q.pop();
    for (j = 1;j<=n;j++){
        if (viz[j] == 0 && c[i][j] - f[i][j] > 0){//arc parcurs in sens direct
            viz[j] = 1;
            T[j] = i;
            q.push(j);
            if(c[j][n] - f[j][n] > 0)fr.push(j);}
        if (viz[j] == 0 && f[j][i] > 0){//arc parcurs in sens invers
            viz[j] = 1;
            T[j] = i;
            q.push(j);
            if(f[j][n]>0)fr.push(j);}}}
 return;
}
void calcdrum(int frCrt){
 int i=0,b=frCrt,a;
 if(c[b][n] - f[b][n]>0) minim = c[b][n] - f[b][n];
 else minim = f[b][n];
 a = T[b];
 while (a!=0){
    if (c[a][b] > f[a][b]){
        if (minim > c[a][b] - f[a][b])
            minim = c[a][b] - f[a][b];}
        else
            if (minim > f[b][a])
                minim = f[b][a];
    i++;
    b = a;
    a = T[b];}
}
int main(){
 int i,j,k,ok=1;
 fin >> n >> m;
 for (i=0;i<m;i++){
    fin >> i >> j;
    fin >> c[i][j];}
 while (ok == 1){
    ok=0;
    bf(); //returneaza 1 daca gaseste un drum
    while(!fr.empty()){
        ok=1;
        int i=fr.front();
        fr.pop();
        calcdrum(i); //calculeaza si minimul
        j=n;
        do{
            if (c[i][j] - f[i][j] > 0)
                f[i][j] += minim;
            else
                f[j][i] -= minim;
            j = i;
            i = T[j];
        }while(T[j]!=0);}}
 int fluxmax = 0;
 for (i=1;i<=n;i++)
    fluxmax += f[1][i];
 fout<<fluxmax<<endl;
 return 0;}