#include <algorithm>
#include <fstream>
#include <iostream>
#include <queue>
#include <set>
#include <vector>
using namespace std;

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

const int MAX_N = 1005;
const int INF = 1 << 30;
int source, sink;

int N, M;
vector<int> graph[MAX_N];
int capacity[MAX_N][MAX_N];
int flow[MAX_N][MAX_N];
int excess[MAX_N];
int height[MAX_N];
int height_frequency[2 * MAX_N];
queue<int> q;
set<int> gaps;

void read_input();
int push_relabel();
void initialize_preflow();
void discharge(int u);
void push(int u, int v);
inline int cf(int u, int v);


int main() {
  read_input();
  fout << push_relabel();
  return 0;
}

void read_input() {
  fin >> N >> M;
  for (int i = 1, a, b, c; i <= M; ++i) {
    fin >> a >> b >> c;
    graph[a].push_back(b);
    graph[b].push_back(a);
    capacity[a][b] = c;
  }
  source = 1;
  sink = N;
}

int push_relabel() {
  initialize_preflow();
  while (!q.empty()) {
    int u = q.front();
    discharge(u);
    q.pop();
  }
  return -excess[source];
}

void initialize_preflow() {
  height[source] = N;
  for (auto v : graph[source]) {
    flow[source][v] = excess[v] = capacity[source][v];
    excess[source] += (flow[v][source] = -capacity[source][v]);
    if (v != sink) {
      q.push(v);
    }
  }

  height_frequency[0] = N - 1;
  height_frequency[N] = 1;
}

void discharge(int u) {
  //magic gap heuristic that reduces the running time
  if (!gaps.empty()) {
    int min_gap = *gaps.begin();
    if (height[u] > min_gap) {
      height[u] = max(height[u], height[source] + 1);
    }
  }
  //remove if unnecessary

  while (excess[u] > 0) {
    int min_height = INF;

    for (auto v : graph[u]) {
      if (cf(u, v) > 0) {
        if (height[u] == height[v] + 1) {
          push(u, v);
          if (v != source && v != sink) {
            q.push(v);
          }
        } else {
          min_height = min(min_height, height[v]);
        }
      }
    }

    if (excess[u] > 0) {
      int old_height = height[u];
      int new_height = min_height + 1;

      height[u] = new_height;

      //also needed for gap heuristic
      height_frequency[old_height] -= 1;
      height_frequency[new_height] += 1;

      if (height_frequency[old_height] == 0 &&
          0 < old_height && old_height < N) {
        gaps.insert(old_height);
      }
      if (height_frequency[new_height] == 1) {
        gaps.erase(new_height);
      }
      //cut here
    }
  }
}

inline void push(int u, int v) {
  int quantity = min(excess[u], cf(u, v));
  flow[u][v] += quantity;
  flow[v][u] -= quantity;
  excess[u] -= quantity;
  excess[v] += quantity;
}

inline int cf(int u, int v) {
  return capacity[u][v] - flow[u][v];
}