#include <fstream>
#include <cstring>
#include <vector>
#include <queue>

using namespace std;

ifstream cin ("maxflow.in");
ofstream cout ("maxflow.out");

struct muchie  {
  int nod, cost, flux;
  muchie *r;
};

//auto cmp = [](muchie _x, muchie _y)  {
//  return _x.cost > _y.cost;
//};

//priority_queue <muchie, vector <muchie>, decltype(cmp)> pq(cmp);

int n, m, ans;
int cost[1005], anterior[1005];
muchie *muchie_ant[1005];

queue <int> q;
vector <muchie> v[1005];

//void afisez_muchii()  {
//  for (int i = 1; i <= n; ++i)  {
//    for (auto it : v[i])  {
//      if (it.flux != 0)
//      cout << i << ' ' << it.nod << /*' ' << it.cost <<*/ ' ' << it.flux << '\n';
//    }
//    cout << '\n';
//  }
//  cout << '\n';
//}

void bfs();

void reconstituire()  {
  while (!q.empty())
    q.pop();
  int nod = n;
  while (nod != 1)  {
//    afisez_muchii();
    muchie_ant[nod] -> flux += cost[n];
    muchie_ant[nod] -> r -> flux -= cost[n];
//    afisez_muchii();
    nod = anterior[nod];
  }
  ans += cost[n];
  bfs();
}

void bfs()  {
  q.push(1);
  memset(anterior, 0, sizeof(anterior));
  memset(cost, 0, sizeof(cost));
  cost[1] = 2e9;
  while (!q.empty())  {
    int nod = q.front();
    q.pop();
    for (int i = 0; i < v[nod].size(); ++i)  {
      auto it = v[nod][i];
      if (cost[it.nod] || it.cost == it.flux || it.flux == 0 && it.cost < 0)
        continue;
      anterior[it.nod] = nod;
      muchie_ant[it.nod] = &v[nod][i];
      if (it.flux <= 0 && it.cost < 0)
        cost[it.nod] = min(cost[nod], - it.flux);
      else
        cost[it.nod] = min(cost[nod], it.cost - it.flux);
      if (it.nod == n)  {
        if (cost[n] > 0)  {
          reconstituire();
        }
        return;
      }
      q.push(it.nod);
    }
  }
}

int main()  {
  cin >> n >> m;
  int x, y, z;
  for (int i = 1; i <= m; ++i)  {
    cin >> x >> y >> z;
    if (x == y)
      continue;
    muchie *aux;
    v[x].push_back({y, z, 0, aux});
    v[y].push_back({x, - z, 0, &v[x].back()});
    v[x].back().r = &v[y].back();
  }
  bfs();
//  afisez_muchii();
  cout << ans;
	return 0;
}