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


int N, M;
vector<vector<int>> graf;
vector<vector<int>> grafcost;
vector<int> tata;
vector<int> viz;

int bfs()
{   tata.resize(N+1,0);
    viz.resize(N+1,0);

    queue<int> q;
     q.push(1);
    tata[1] = 0;

    while(!q.empty())
    {
        int nod = q.front();
        q.pop();
        if(nod == N)
            return 1;

        for(int i = 0; i < graf[nod].size(); i++)
        {
            int vecin = graf[nod][i];
            if(viz[vecin] == 0 && grafcost[nod][vecin] > 0)
            {
                q.push(vecin);
                tata[vecin] = nod;
                viz[vecin] = 1;
            }
        }
    }
    return 0;
}

int flowmax()
{  int flow_maxim , flow_min , nod , vecin;
    flow_maxim = 0;
    while(bfs())
    {
      for ( int i = 0 ; i < graf[N].size() ; i++ )
      {
          if(grafcost[graf[N][i]][N] > 0  && viz[graf[N][i]] == 1)
          {  nod = graf[N][i];
                flow_min = grafcost[nod][N];
                while(tata[nod])
                {
                    vecin = tata[nod];
                    flow_min = min(flow_min, grafcost[vecin][nod]);
                    nod = vecin;
                }
                flow_maxim += flow_min;
                nod = graf[N][i];
                grafcost[nod][N] -= flow_min;
                grafcost[N][nod] += flow_min;
                while(nod != 1)
                {
                    vecin = tata[nod];
                    grafcost[vecin][nod] -= flow_min;
                    grafcost[nod][vecin] += flow_min;
                    nod = vecin;
                }
          }

      }
    }
    return flow_maxim;



}
int main() {
    fin>> N >> M;
    graf.resize(N+1);
    grafcost.resize(N+1, vector<int>(N+1));


    for ( int i = 1 ; i <= M; ++ i) {
         int x, y, z;
         fin>> x >> y >> z;
        graf[x].push_back(y);
        graf[y].push_back(x);
        grafcost[x][y] += z;

    }

    fout<<flowmax() + 1;

    return 0;
}