#include <fstream>
#include <limits>
#include <algorithm>
#include <queue>

using namespace std;

#define MAX_M 5000
#define MAX_N 1000

typedef struct {
  uint32_t v, next;
} cell;

uint32_t N, M;
uint32_t adj[MAX_N + 1];
cell list[MAX_M + 1];
uint32_t parent[MAX_N + 1];
uint32_t capacity[MAX_N + 1][MAX_N + 1];
uint32_t flow[MAX_N + 1][MAX_N + 1];
queue<uint32_t> q;

void addEdge(uint32_t index, uint32_t u, uint32_t v) {
  list[index].v = v;
  list[index].next = adj[u];
  adj[u] = index;
}

uint32_t check(uint32_t u, uint32_t v) {
  return (capacity[u][v] & 1) ? ((capacity[u][v] >> 1) - flow[u][v]) : flow[u][v];
}

bool bfs(uint32_t source, uint32_t sink) {
  for (uint32_t index = 1; index <= N; ++index)
    parent[index] = 0;
  q.push(source);
  while (!q.empty()) {
    uint32_t u = q.front();
    q.pop();
    
    if (u == sink) {
      while (!q.empty()) q.pop();
      return true;
    }
    for (uint32_t pos = adj[u]; pos; pos = list[pos].next) {
      uint32_t v = list[pos].v, residualFlowOnEdge = check(u, v);
      if ((!parent[v]) && (residualFlowOnEdge)) {
        parent[v] = u;
        q.push(v);
      }
    }
  }
  
  return false;
}

void ford_fulkerson(uint32_t source, uint32_t sink) {
  unsigned count = 0;
  do {
    bool residualGraphHasPath = bfs(source, sink);
    if (!residualGraphHasPath)
      return;
    uint32_t minim = numeric_limits<uint32_t>::max();
    for (uint32_t node = sink; node != source; node = parent[node])
      minim = min(minim, check(parent[node], node));
    
    for (uint32_t node = sink; node != source; node = parent[node]) {
      if (capacity[parent[node]][node] & 1)
        flow[parent[node]][node] += minim;
      else
        flow[parent[node]][node] -= minim;
    }
  } while (true);
}

int main(void) {
  ifstream cin("maxflow.in");
  ofstream cout("maxflow.out");
  cin >> N >> M;
  for (uint32_t index = 1; index <= M; ++index) {
    uint32_t u, v, cap;
    cin >> u >> v >> cap;
    addEdge(index, u, v);
    addEdge(index + M, v, u);
    capacity[u][v] = (cap << 1) + 1;
    capacity[v][u] = (cap << 1);
  }
  ford_fulkerson(1, N);
  
  uint32_t maxFlow = 0;
  for (uint32_t index = 1; index <= N; ++index) {
    if (capacity[index][N] & 1)
      maxFlow += flow[index][N];
  }
  cout << maxFlow << endl;
  return 0;
}