#include <bits/stdc++.h>
using namespace std;
ifstream fin("maxflow.in");
ofstream fout("maxflow.out");
//ifstream fin("flux1.in");
//ofstream fout("flux1.out");

#define maxx INT_MAX
#define N 1001
int cap[N][N], flux[N][N];
vector<int> t;
int n, m;

int bfs (int s, int d){
    deque<int> Q;
    vector<int> use(n+1, 0);
    t.assign(n+1, 0);
    Q.push_back(s);
    use[s]=1;
    while(!Q.empty()){
        int nod = Q.front();
        Q.pop_front();
        if(nod==d) break;
        for(int i=1; i<=n; i++){
            if(cap[nod][i]!=0 and !use[i]){
                if((cap[nod][i]-flux[nod][i])>0){
                    Q.push_back(i);
                    t[i]=nod;
                    use[i]=1;
                }
            }
        }
    }
    if(t[d]) return 1;
    return 0;
}

int edmond_karp(int s, int d){
    int flow = 0;
    int i, mini;
    while(bfs(s,d)){
        mini= maxx;
        i=d;
        while(t[i]!=0){
            if((cap[t[i]][i] - flux[t[i]][i] )< mini)
                mini = (cap[t[i]][i] - flux[t[i]][i]);
            i=t[i];
        }
        i=d;
         while(t[i]!=0){
            flux[t[i]][i] += mini;
            flux[i][t[i]] -= mini;
            i=t[i];
        }
        flow += mini;
    }
    return flow;
}

int dinic(int s, int d){
    int flow=0;
    int i,j, mini;
    while(bfs(s,d)){
        //cout<<"ad";
        for(j=1; j<=n; ++j){
            if((cap[j][d]-flux[j][d])>0){
                mini=maxx;
                if((cap[j][d]-flux[j][d])<mini)
                    mini=(cap[j][d]-flux[j][d]);

                i=j;
                 while(t[i]!=0){
                    if((cap[t[i]][i] - flux[t[i]][i])< mini)
                        mini = (cap[t[i]][i] - flux[t[i]][i]);
                    i=t[i];
                }

                if(mini==maxx) continue;
                    flux[j][d] += mini;
                    flux[d][j] -= mini;

                i=j;
                 while(t[i]!=0){
                    flux[t[i]][i] += mini;
                    flux[i][t[i]] -= mini;
                    i=t[i];
                }
                flow += mini;
            }
        }
    }
    return flow;
}

int main()
{
    int s, d,x,y,c;
    fin>>n>>m;
    s=1;
    d=n;
//    fin>>s>>d;
    for(int i=1; i<=m; i++){
        fin>>x>>y>>c;
        cap[x][y]=c;
        cap[y][x]=-c;
    }
    fout<<edmond_karp(s,d);
    return 0;
}