#include <bits/stdc++.h>
#include <unordered_map>
#include <map>

using namespace std;

ifstream fin("maxflow.in");
ofstream fout("maxflow.out");
//-----------------------------------------
#define ll long long
#define pii pair<int, int>
#define pll pair<long long, long long>
#define vi vector<int>
#define vll vector<long long>
#define mii map<int, int>
#define si set<int>
#define sc set<char>
//-----------------------------------------
#define f(i,s,e) for(int i=s;i<=e;++i)
#define nf(i,s,e) for(i=s;i<e;++i)
#define rf(i,e,s) for(i=e;i>=s;--i)
#define pb push_back
#define eb emplace_back
#define fi first
#define se second
#define sp <<" "
//------------------------------------------
const int NMAX = 1e3 + 5;
const int KMAX = 1e1 + 5;
const int MOD = 1e9 + 7;
const int INF = 0x3f3f3f3f;
//------------------------------------------
int n,m,S,D,flux;
int c[NMAX][NMAX],f[NMAX][NMAX],t[NMAX];
vi L[NMAX];
//------------------------------------------
void read() {
fin>>n>>m;
for(int i=1;i<=m;++i){
   int x,y,cost;
   fin>>x>>y>>cost;
   c[x][y]=cost;
   L[x].pb(y);
   L[y].pb(x);
 }
 S=1,D=n;
 fin.close();
}
int BFS(int s, int d){
    int pr, ul, nod, q[NMAX];
    memset(t, 0, sizeof(t));
    pr = ul = 0;
    q[pr] = s;
    t[s] = -1;
    while (pr <= ul){
        nod = q[pr++];
        for (auto i : L[nod])
            if (t[i] == 0 && c[nod][i] > f[nod][i]){
                q[++ul] = i;
                t[i] = nod;
            }
    }
    if (t[d] != 0) return 1;
    return 0;
}
void Dinic(){
  int r;
  for(flux=0;BFS(S,D);){
    for(int i=1;i<=n;++i){
       if(t[i]==-1 || c[i][D]<=f[i][D]) continue;
       r=c[i][D]-f[i][D];
       for(int j=i;j!=S && j>0; j=t[j])
          r=min(r,c[t[j]][j]-f[t[j]][j]);
       if(r==0) continue;
       f[i][D]+=r;
       f[D][i]-=r;
       for(int j=i;j!=S;j=t[j]){
        f[t[j]][j]+=r;
        f[j][t[j]]-=r;
       }
       flux+=r;
  }
 }
}
void solve() {
 Dinic();
 fout<<flux;
 fout.close();
}
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    read();
    solve();
    return 0;
}