#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, 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);

namespace {
  const int BUFFER_LIMIT = 1000000;

  int char_counter = BUFFER_LIMIT - 1;
  char buffer[BUFFER_LIMIT];

  inline void check_buffer() {
    (++char_counter == BUFFER_LIMIT) ? (fin.read(buffer, BUFFER_LIMIT), char_counter = 0) : (1);
  }

  void parse_integer(int &x){
    bool neg = false;
    while (!((buffer[char_counter] >= '0' && buffer[char_counter] <= '9') || (buffer[char_counter] == '-' ))) check_buffer();

    if (buffer[char_counter] == '-') {
      check_buffer();
      neg = true;
    }

    for (x = 0; (buffer[char_counter] >= '0' && buffer[char_counter] <= '9'); x *= 10, x += (buffer[char_counter] - '0'), check_buffer());

    if (neg) {
        x = -x;   
    }
  }
}

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

  void read_input() {
    // fin >> N >> M;
    parse_integer(N), parse_integer(M);
    for (int i = 1, a, b, c; i <= M; ++i) {
      // fin >> a >> b >> c;
      parse_integer(a), parse_integer(b), parse_integer(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;
    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) {
    int min_height, v;
    while (excess[u] > 0) {
      min_height = INF;

      for (unsigned int i = 0; i < graph[u].size(); ++i) {
        v = graph[u][i];
        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];
  }