#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);
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 = -excess[source];
  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) {
  while (excess[u] > 0) {
    int min_height = INF;
    
    for (int v = 1; v <= N; ++v) {
      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) {
      height[u] = min_height + 1;
    }
  }
}

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