#include <iostream>
#include <fstream>
#include <queue>

using namespace std;

ifstream in("maxflow.in");
ofstream out("maxflow.out");

int const NMAX = 1000;

//I am in g[from][index]
struct Edge {
  int to;
  int rev; //Inverse edge index within g[to]
  int cap;
  int flow;
};

// g[1][7] = {2, 6, 10, 0}
// g[2][6] = {1, 7,  0, 0};

int n, m, src, dest;
vector<Edge> g[1 + NMAX];
int cap[1 + NMAX][1 + NMAX];

int dist[1 + NMAX]; //this is how we model the level graph
int rem[1 + NMAX]; //remember the index at which DFS left off

//build the level graph
bool bfs() {
  queue<int> q;
  q.push(src);
  for(int i = 1; i <= n; i++) {
    dist[i] = INT_MAX;
  }
  dist[src] = 0;
  while(!q.empty()) {
    int from = q.front();
    q.pop();
    for(Edge e : g[from]) {
      if(e.flow < e.cap && dist[e.to] == INT_MAX) {
        dist[e.to] = dist[from] + 1;
        q.push(e.to);
      }
    }
  }
  //out << dist[dest] << "\n";
  return (dist[dest] != INT_MAX);
}

int dfs(int from, int deltaFlow) { //deltaflow remember deltaFlow minimum
  if(from == dest) {
    return deltaFlow;
  } else {
    for(int &i = rem[from]; i < g[from].size(); i++) {
      Edge &e = g[from][i];
      if(dist[e.to] == dist[from] + 1 && e.flow < e.cap) { //TODO: think about it
        int addFlow = dfs(e.to, min(deltaFlow, e.cap - e.flow));
        if(addFlow > 0) {
          e.flow += addFlow;
          Edge &rev = g[e.to][e.rev];
          rev.flow -= addFlow;
          return addFlow;
	   }
      }
    }
    return 0;
  }
}

int dinic() {
  int ans = 0;
  while(bfs()) {
    for(int i=0; i<n; i++) {
      rem[i] = 0;
    }
    int delta = dfs(src, INT_MAX);
    while(delta > 0) {
      ans += delta;
      delta = dfs(src, INT_MAX);
    }
  }
  return ans;
}

int main() {
  in >> n >> m;
  for(int i = 1; i <= m; i++) {
    int x, y, z;
    in >> x >> y >> z;
    cap[x][y] = z;
  }
  src = 1, dest = n;
  for(int x = 1; x <= n; x++) {
    for(int y = x+1; y <= n; y++) {
      if(cap[x][y] != 0 || cap[y][x] != 0) {
        g[x].push_back({y, (int)g[y].size(), cap[x][y], 0});
        g[y].push_back({x, (int)g[x].size()-1, cap[y][x], 0});
        //out << x << ": " << g[x].back().to << " " << g[x].back().rev << " " << g[x].back().cap << " " << g[x].size()-1 << "\n";
        //out << y << ": " << g[y].back().to << " " << g[y].back().rev << " " << g[y].back().cap << " " << g[y].size()-1 << "\n";
      }
    }
  }
  out << dinic();
  return 0;
}