#include<fstream>
#include<algorithm>
#include<cstring>
#include<queue>
#define abs(a) ((a)>=0?(a):(-(a)))
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
using namespace std;
ifstream in("maxflow.in");
ofstream out("maxflow.out");
const int Nmax = 1005;
const int Mmax = 10005;
int pred[Nmax],fr[Nmax];
int C[Nmax][Nmax],c[Nmax][Nmax];
struct much{
    int x,y;
} V[Mmax];
int N,M;
queue<int> q;
struct list{
    int vf[Mmax],urm[Mmax],lst[Mmax],m;
    void push(int& x,int& y){
        vf[++m]=y;
        urm[m]=lst[x];
        lst[x]=m;
    }
} G;
int bfs(){
    while(!q.empty()) q.pop();
    memset(pred,0,sizeof(pred));
    q.push(1);
    pred[1]=-1;
    while(!q.empty()){
        int x=q.front(); q.pop();
        for(int i=G.lst[x];i!=0;i=G.urm[i]){
            int it=G.vf[i];
            if(pred[it]==0 && c[x][it]<C[x][it]){
                pred[it]=x;
                q.push(it);
            }
        }
    }
    return pred[N]!=0;
}
int Fr[Nmax];
int addpath(int x){
    int y=x,Min=( C[x][N]-c[x][N] );
    while(y!=1){
        Min=min(Min,C[pred[y]][y]-c[pred[y]][y]);
        if(Min==0) return 0;
        y=pred[y];
    }
    c[x][N]+=Min;
    c[N][x]-=Min;
    y=x;
    while(y!=1){
        c[pred[y]][y]+=Min;
        c[y][pred[y]]-=Min;
        y=pred[y];
    }
    return Min;
}
int mark[2][Nmax];
int critic(int x,int y){
    return abs(c[x][y])==C[x][y];
}
void Dfs(int A[],int x){
    A[x]=1;
    for(int i=G.lst[x];i!=0;i=G.urm[i]){
        int it=G.vf[i];
        if(!A[it] && !critic(x,it)) Dfs(A,it);
    }
}
int Sol[Mmax];
int main(){
    in>>N>>M;
    for(int i=1;i<=M;i++){
        int x,y,z;
        in>>x>>y>>z;
        G.push(x,y);
        G.push(y,x);
        V[i].x=x;V[i].y=y;
        //C[x][y]=C[y][x]=z;
        C[x][y]=z;
        //if(x==N) Fr[++Fr[0]]=y;
        if(y==N) Fr[++Fr[0]]=x;
    }
    int MF=0; while(bfs()) for(int i=1;i<=Fr[0];i++) MF+=addpath(Fr[i]);
    out<<MF<<'\n';
    /*
    //for(int i=1;i<=M;i++) out<<V[i].x<<' '<<V[i].y<<' '<<C[V[i].x][V[i].y]<<' '<<c[V[i].x][V[i].y]<<'\n';
    Dfs(mark[0],1);
    Dfs(mark[1],N);
    //for(int i=1;i<=N;i++) out<<mark[0][i]<<' ';out<<'\n';
    //for(int i=1;i<=N;i++) out<<mark[1][i]<<' ';out<<'\n';
    for(int i=1;i<=M;i++){
        int x=V[i].x,y=V[i].y;
        if( critic(x,y) && (mark[0][x]+mark[1][y]==2) || (mark[1][x]+mark[0][y]==2) ) Sol[++Sol[0]]=i;
    }
    sort(Sol+1,Sol+Sol[0]+1);
    out<<Sol[0]<<'\n';
    for(int i=1;i<=Sol[0];i++) out<<Sol[i]<<'\n';
    */
    return 0;
}