#include <algorithm>
#include <fstream>
#include <iostream>
#include <queue>
#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];
vector<int>::iterator seen[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);
    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);
    }
  }

  for (int i = 1; i <= N; ++i) {
    seen[i] = graph[i].begin();
  }
}

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

    while (seen[u] != graph[u].end()) {
      int v = *seen[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]);
        }
      }
      ++seen[u];
    }

    if (excess[u] > 0) {
      height[u] = min_height + 1;
      seen[u] = graph[u].begin();
    }
  }
}

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