#include <fstream>
#include <iostream>
#include <algorithm>
#include <climits>
#include <queue>

using namespace std;

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

int const nmax = 1000;

int n, m, src, dest;
int cap[1 + nmax][1 + nmax];
int dist[1 + nmax]; //distance in BFS
queue<int> q; //queue in BFS

int rem[1 + nmax]; //dfs implementation

struct Edge {
    int to;
    int rev; //order number of reverse edge in g[to]
    int flow;
    int cap;
};

vector<Edge> g[1 + nmax];

void addedge(int from, int to) {
  Edge a = {to, g[to].size(), 0, cap[from][to]};
  Edge b = {from, g[from].size(), 0, cap[to][from]};
  g[from].push_back(a);
  g[to].push_back(b);
}

bool dinicbfs() {
  fill(dist + 1, dist + n + 1, -1);
  dist[src] = 0;
  q.push(src);
  while (!q.empty()) {
    int from = q.front();
    for (int j = 0; j < g[from].size(); j++) {
      Edge &e = g[from][j];
      int to = e.to;
      if (dist[to] < 0 && e.flow < e.cap) {
        dist[to] = dist[from] + 1;
        q.push(to);
      }
    }
    q.pop();
  }
  return (0 <= dist[dest]);
}

int dinicdfs(int from, int deltaflow) {
  if (from == dest)
    return deltaflow;
  for (int i = rem[from]; i < g[from].size(); i++) {
    Edge &e = g[from][i];
    if (e.flow < e.cap) {
      int to = e.to;
      if (dist[to] == dist[from] + 1) {
        int addflow = dinicdfs(to, min(deltaflow, e.cap - e.flow));
        if (addflow > 0) {
          e.flow += addflow;
          g[to][e.rev].flow -= addflow;
          return addflow;
        }
      }
    }
  }
  return 0;
}

int maxflow() {
  int i = 0, result = 0;
  while (dinicbfs()) {
    i++;
    fill(rem + 1, rem + n + 1, 0);
    while (int delta = dinicdfs(src, INT_MAX)) {
      result += delta;
    }
  }

  return result;
}

int main() {
  in >> n >> m;
  src = 1;
  dest = n;

  for (int i = 1; i <= m; i++) {
    int from, to, cost;
    in >> from >> to >> cost;
    cap[from][to] = cost;
  }

  for (int i = 1; i < n; i++) {
    for (int j = i + 1; j <= n; j++) {
      if (cap[i][j] != 0 || cap[j][i] != 0) {
        addedge(i, j);
      }
    }
  }
  out << maxflow() << endl;
  return 0;
}