# include <fstream>
# include <vector>
# include <queue>
# define DIM 1010
# define f first
# define s second
using namespace std;
ifstream fin("maxflow.in");
ofstream fout("maxflow.out");
vector<int> Lista[DIM];
queue<int> q;
int c[DIM][DIM],f[DIM][DIM],t[DIM],Marcat[DIM],n,m,x,y,cost,i,mn,sol;
bool flux(){
    for(int i=1;i<=n;i++)
        Marcat[i]=t[i]=0;
    q.push(1);
    Marcat[1]=1;
    while(!q.empty()){
        int nc=q.front();
        q.pop();
        for(int i=0;i<Lista[nc].size();i++){
            int nv=Lista[nc][i];
            if(Marcat[nv]==0&&c[nc][nv]>f[nc][nv]){
                q.push(nv);
                t[nv]=nc;
                Marcat[nv]=1;
            }
        }
    }
    return Marcat[n];
}
int main () {
    fin>>n>>m;
    for(i=1;i<=m;i++){
        fin>>x>>y>>cost;
        Lista[x].push_back(y);
        Lista[y].push_back(x);
        c[x][y]=cost;
    }
    while(flux()){
      flux();
        for(i=0;i<Lista[n].size();i++){
            int nc=Lista[n][i];
            if(f[nc][n]<c[nc][n]&&Marcat[nc]){
                mn=c[nc][n]-f[nc][n];
                for(x=nc;t[x];x=t[x])
                    mn=min(mn,c[t[x]][x]-f[t[x]][x]);
                sol+=mn;
                f[nc][n]+=mn;
                f[n][nc]-=mn;
                for(x=nc;t[x];x=t[x]){
                    f[t[x]][x]+=mn;
                    f[x][t[x]]-=mn;
                }
            }
        }
    }
    fout<<sol<<"\n";
    return 0;
}