#include <vector>
#include <fstream>
#include <memory>
#include <unordered_map>
#include <queue>
#include <limits>
#include <iostream>
#include <string>


using namespace std;

class ResidualEdge {
  public:

    ResidualEdge(int source, int destination, int flux, int capacity) {
      this->source = source;
      this->destination = destination;
      this->flux = flux;
      this->capacity = capacity;
    }

    int source;
    int destination;

    int flux;
    int capacity;

    shared_ptr<ResidualEdge> backwardEdge;
};

class ResidualGraph {
  public:
    int source;
    int sink;
    vector<shared_ptr<ResidualEdge>> edges;

    unordered_map<int, vector<shared_ptr<ResidualEdge>>> edgesBySource;


    ResidualGraph(int source, int sink) {
      this->source = source;
      this->sink = sink;
    }

    void addEdge(int source, int destination, int flux, int capacity) {
      shared_ptr<ResidualEdge> positiveEdge = shared_ptr<ResidualEdge>(new ResidualEdge(source, destination, flux, capacity));
      shared_ptr<ResidualEdge> negativeEdge = shared_ptr<ResidualEdge>(new ResidualEdge(destination, source, capacity - flux, capacity));

      positiveEdge->backwardEdge = negativeEdge;
      negativeEdge->backwardEdge = positiveEdge;

      edgesBySource[source].push_back(positiveEdge);
      edgesBySource[destination].push_back(negativeEdge);

      edges.push_back(positiveEdge);
      edges.push_back(negativeEdge);
    }

    int getTotalFluxThroughTheNetwork() {
      int totalFlux = 0;

      for (const auto &edge : edgesBySource[source]) {
        totalFlux += edge->flux;
      }

      return totalFlux;
    }
};



vector<shared_ptr<ResidualEdge>> findPath(ResidualGraph& graph, bool& errorFlag) {
  vector<shared_ptr<ResidualEdge>> path;

  unordered_map<int, bool> visited;
  queue<pair<int, int>> fatherSonQueue;
  queue<shared_ptr<ResidualEdge>> edgesQueue;

  unordered_map<int, shared_ptr<ResidualEdge>> parentEdge;

  fatherSonQueue.push(make_pair(-1, graph.source));
  edgesQueue.push(nullptr);

  while (!fatherSonQueue.empty()) {
    int currentFather = fatherSonQueue.front().first;
    int currentChild = fatherSonQueue.front().second;
    // cout << currentFather << " " << currentChild << endl;
    shared_ptr<ResidualEdge> currentEdge = edgesQueue.front();

    fatherSonQueue.pop();
    edgesQueue.pop();


    if (visited[currentChild]) {
      continue;
    }

    visited[currentChild] = true;

  
    if (currentFather != - 1 && currentEdge != nullptr) {
      parentEdge[currentChild] = currentEdge;
    }


    for (const auto& residualEdge : graph.edgesBySource[currentChild]) {
      
      int nextNode = residualEdge->destination;

      if (residualEdge->capacity - residualEdge->flux > 0) {
        fatherSonQueue.push(make_pair(currentChild, nextNode));
        edgesQueue.push(residualEdge);
      }
    }
  }

  // cout << graph.sink << endl;

  if (!visited[graph.sink]) {
    errorFlag = true;
  }

  // find the actual path

  int node = graph.sink;

  while (!errorFlag && node != graph.source) {
    // cout << node << endl;
    path.push_back(parentEdge[node]);
    node = parentEdge[node]->source;
  }

  // cout << endl;

  return path;
}


void fordFulkerson(ResidualGraph& graph) {
  while (true) {
    bool errorFlag = false;
    vector<shared_ptr<ResidualEdge>> path = findPath(graph, errorFlag);

    // cout << errorFlag << endl;

    if (errorFlag) {
      break;
    }

    // find the minimum residual capacity in the path
    int minimumResidualCapacity = numeric_limits<int>::max();

    for (const auto& edge : path) {
      minimumResidualCapacity = min(minimumResidualCapacity, edge->capacity - edge->flux);
    }

    // augment the path with the minimum residual capacity

    for (const auto& edge : path) {
      edge->flux += minimumResidualCapacity;
      edge->backwardEdge->flux -= minimumResidualCapacity;
    }
  }
}

int main(int argc, char* argv[]) {
  ifstream in("maxflow.in");
  ofstream out("maxflow.out");

  // build the residual graph

  int n, m;
  in >> n >> m;

  int source = 1;
  int destination = n;

  ResidualGraph graph = ResidualGraph(source, destination);

  for (int i = 1; i <= m; i++) {
    int x, y, c;
    in >> x >> y >> c;

    graph.addEdge(x, y, 0, c);
  }

  fordFulkerson(graph);

  // for (const auto& edge : graph.edges) {
  //   out << edge->source << " -> " << edge->destination << ": " + to_string(edge->flux) + " / " + to_string(edge->capacity) << endl;
  // }

  out << graph.getTotalFluxThroughTheNetwork();

  in.close();
  out.close();

  return 0; 
}