//push relabel algorithm
//time complexity: O(N ^ 3)

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

#define FORIT(it,v) for(typeof((v).begin())it=(v).begin();it!=(v).end();++it)
ifstream fin("maxflow.in");
ofstream fout("maxflow.out");

const int MAX_N = 1005;
const int INF = 1 << 30;
int source = 1, 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];
queue<int> q;

void read_input();
int push_relabel();
void initialize_preflow();
void discharge(int u);
void push(int u, int v);
void relabel(int u);
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);
    capacity[a][b] = c;
  }
  sink = N;
}

int push_relabel() {
  initialize_preflow();

  while (!q.empty()) {
    int u = q.front();
    discharge(u);
    q.pop();
  }
  int max_flow = 0;
  FORIT (it, graph[source]) {
    max_flow += flow[source][*it];
  }
  return max_flow;
}

void initialize_preflow() {
  height[source] = N;
  FORIT (it, graph[source]) {
    int v = *it;
    flow[source][v] = excess[v] = capacity[source][v];
    excess[source] += (flow[v][source] = -capacity[source][v]);
    if (v != sink) {
      q.push(v);
    }
  }
}

void discharge(int u) {
  bool need_relabel = false;
  while (excess[u] > 0) {
    if (need_relabel) {
      relabel(u);
    }
    need_relabel = true;
    FORIT (it, graph[u]) {
      int v = *it;
      if (cf(u, v) > 0 && height[u] == height[v] + 1) {
        push(u, v);
        if (v != source && v != sink) {
          q.push(v);
        }
        need_relabel = false;
      }
    }
  }
}

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;
}

void relabel(int u) {
  int min_height = INF;
  FORIT (it, graph[u]) {
    int v = *it;
    if (cf(u, v) > 0) {
      min_height = min(min_height, height[v]);
    }
  }
  height[u] = min_height + 1;
}

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