#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 level[N];
vector<int> adc[N];
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 or cap[i][nod]!=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 bfs_d (int s, int d){
    deque<int> Q;
    for (int i = 1; i <= n; i++)
        level[i] = -1;
    Q.push_back(s);
    level[s]=0;
    while(!Q.empty()){
        int nod = Q.front();
        Q.pop_front();
        if(nod==d) break;
        for(int i=0; i<adc[nod].size(); i++){
            int vecin= adc[nod][i];
            if(level[vecin]<0 && ((cap[nod][vecin]-flux[nod][vecin])>0)){
                Q.push_back(vecin);
                level[vecin]= level[nod]+1;
            }
        }
    }
    if(level[d]>=0) return 1;
    return 0;
}

int dfs_d(int u, int d, int minc, int start[]){
    if(u==d) return minc;

    for(; start[u]<adc[u].size(); start[u]++){
        int vecin = adc[u][start[u]];
        if(level[vecin]==level[u] +1 and flux[u][vecin]<cap[u][vecin]){
            int c_flow = min(minc, cap[u][vecin]-flux[u][vecin]);
            int temp_flow = dfs_d(vecin, d, c_flow, start);
            if(temp_flow>0){
                flux[u][vecin] +=  temp_flow;
                flux[vecin][u] -=  temp_flow;
                return temp_flow;
            }
        }
    }
    return 0;
}

int dinic(int s, int d){
    if(s==d) return -1;

    int flow = 0;

    while(bfs_d(s,d)){
        int start[N]={0};
        while(int f = dfs_d(s,d,maxx,start)){
            flow+=f;
        }
    }
    return flow;
}

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 main()
{
    int s,d,x,y,c;
    fin>>n>>m;
    s=1;
    d=n;
    for(int i=1; i<=m; i++){
        fin>>x>>y>>c;
        adc[x].push_back(y);
        adc[y].push_back(x);
        cap[x][y]=c;
    }
    fout<<dinic(s,d);
    return 0;
}