#include <bits/stdc++.h>

using namespace std;
int n, m, i, j, k;
long long out=0LL, mx=0LL;
int graph[1001][1001], flow[1001][1001], cnt[1001];
queue<int> q;

void read();
void solve();
void write();
bool bfs();
int dfs(int node, int val);
int main()
{
    read();
    solve();
    write();
    return 0;
}
void read(){
    freopen("maxflow.in", "r", stdin);
    scanf("%d%d", &n, &m);
    for(i=1; i<=m; ++i){
        int x, y, f;
        scanf("%d%d%d", &x, &y, &f);
        flow[x][y]+=f;
        if(x==1) mx+=f;
    }
    return;
}
void solve(){
    while(bfs()==true) out=out+dfs(1, mx-out);
    return;
}
void write(){
    freopen("maxflow.out", "w", stdout);
    printf("%lld", out);
}
bool bfs(){
    while(!q.empty()) q.pop();
    q.push(1);
    for(int i=1; i<=n; ++i) graph[i][0]=cnt[i]=0;
    cnt[1]=1;
    while(!q.empty()){
        int init=q.front(); q.pop();
        if(init==n) return true;
        for(int i=1; i<=n; ++i) if(flow[init][i]){
            if(!cnt[i]){
                cnt[i]=cnt[init]+1;
                graph[init][++graph[init][0]]=i;
                q.push(i);
            }
            else if(cnt[i]==cnt[init]+1) graph[init][++graph[init][0]]=i;
        }
    }
    return false;
}
int dfs(int node, int val){
    int ret=0;
    if(!val) return 0;
    if(node==n) return val;
    for(int j=1; j<=n; ++j)if(flow[node][graph[node][j]]){
        int i=graph[node][j];
        int elim=dfs(i, min(val, flow[node][i]));
        val-=elim;
        flow[node][i]-=elim;
        flow[i][node]+=elim;
        ret+=elim;
    }
    return ret;
}