#include <bits/stdc++.h>

using namespace std;

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

void usain_bolt() {
  ios::sync_with_stdio(false);
  std::cin.tie(nullptr);
}

struct Vertex {
  int excess;
  int flow;
  int height;
};

void solve() {
  int n, m;
  fin >> n >> m;
  vector<vector<int>> g(n + 1, vector<int>(n + 1, 0));
  for (int i = 0; i < m; ++i) {
    int x, y, c;
    fin >> x >> y >> c;
    g[x][y] = c;
  }
  int nExt = n;
  for (int i = 1; i <= n; ++i) {
    for (int j = i + 1; j <= n; ++j) {
      if (g[i][j] && g[j][i]) {
        nExt += 1;
      }
    }
  }
  vector<vector<int>> gExt(nExt + 1, vector<int>(nExt + 1, 0));
  vector<vector<int>> flow(nExt + 1, vector<int>(nExt + 1, 0));
  vector<vector<int>> gAdj(nExt + 1, vector<int>());
  vector<Vertex> nodes(nExt + 1);
  for (int i = 1; i <= n; ++i) {
    for (int j = i + 1; j <= n; ++j) {
      if (g[i][j] && g[j][i]) {
        gExt[i][nExt] = g[i][j];
        gExt[nExt][j] = g[i][j];
        gExt[j][i] = g[j][i];
        gAdj[i].push_back(nExt);
        gAdj[nExt].push_back(i);
        gAdj[nExt].push_back(j);
        gAdj[j].push_back(nExt);
        gAdj[j].push_back(i);
        gAdj[i].push_back(j);
        nExt -= 1;
        continue;
      }
      if (g[i][j]) {
        gExt[i][j] = g[i][j];
        gAdj[i].push_back(j);
        gAdj[j].push_back(i);
      } else if (g[j][i]) {
        gExt[j][i] = g[j][i];
        gAdj[j].push_back(i);
        gAdj[i].push_back(j);
      }
    }
  }
  nExt = int(gExt.size()) - 1;
  nodes[1].height = nExt;
  nodes[1].excess = 0;
  for (int i = 2; i <= nExt; ++i) {
    nodes[i].height = 0;
    nodes[i].excess = 0;
    if (gExt[1][i]) {
      nodes[i].excess = gExt[1][i];
      nodes[1].excess -= gExt[1][i];
      flow[1][i] = gExt[1][i];
    }
  }
  
  constexpr int INF = 1e9;
  while (1) {
    bool finish = true;
    for (int i = 2; i <= nExt; ++i) {
      if (i == n) {
        continue;
      }
      if (!nodes[i].excess) {
        continue;
      }
      finish = false;
      bool raise = false;
      for (auto j : gAdj[i]) {
        bool downhill = nodes[i].height == (nodes[j].height + 1);
        int transfer = nodes[i].excess;
        if (gExt[i][j]) {
          transfer = min(transfer, gExt[i][j] - flow[i][j]);
          if (downhill) {
            flow[i][j] += transfer;
          }
        } else {
          transfer = min(transfer, flow[j][i]);
          if (downhill) {
            flow[j][i] -= transfer;
          }
        }
        if (downhill) {
          nodes[i].excess -= transfer;
          nodes[j].excess += transfer;
        }
        if (transfer && !downhill) {
          raise = true;
          continue;
        }
      }
      if (!raise || nodes[i].excess == 0) {
        continue;
      }
      int mnHeight = INF;
      for (auto j : gAdj[i]) {
        if (gExt[i][j] - flow[i][j] > 0 || (gExt[j][i] && flow[j][i])) {
          mnHeight = min(mnHeight, nodes[j].height);
        }
      }
      if (mnHeight < INF) {
        nodes[i].height = 1 + mnHeight;
        --i;
      }
    }
    if (finish) {
      break;
    }
  }
  int sol = 0;
  for (int i = 1; i <= nExt; ++i) {
    if (gExt[i][n]) {
      sol += flow[i][n];
    }
  }
  fout << sol << '\n';

  return;
}

int main()
{
  int tt;
  // cin >> tt;
  tt = 1;
  while (tt--)
  {
    solve();
  }

  return 0;
}