#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));
  vector<Vertex> nodes(n + 1);
  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));
  gExt = g;
  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];
        nExt -= 1;
        continue;
      }
      if (g[i][j]) {
        gExt[i][j] = g[i][j];
      } else if (g[j][i]) {
        gExt[j][i] = g[j][i];
      }
    }
  }
  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];
      flow[i][1] = -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 found = false;
      for (int j = 1; j <= nExt; ++j) {
        if (nodes[i].height != nodes[j].height + 1) {
          continue;
        }
        if (!gExt[i][j] && !gExt[j][i]) {
          continue;
        }
        int transfer = nodes[i].excess;
        if (gExt[i][j]) {
          transfer = min(transfer, gExt[i][j] - flow[i][j]);
          flow[i][j] += transfer;
          flow[j][i] -= transfer;
        } else {
          transfer = min(transfer, flow[j][i]);
          flow[j][i] -= transfer;
          flow[i][j] += transfer;
        }
        nodes[i].excess -= transfer;
        nodes[j].excess += transfer;
        if (transfer) {
          found = true;
        }
      }
      if (found) {
        continue;
      }
      int mnHeight = INF;
      for (int j = 1; j <= nExt; ++j) {
        if (gExt[i][j] - flow[i][j] > 0 || (flow[j][i] && gExt[j][i])) {
          mnHeight = min(mnHeight, nodes[j].height);
        }
      }
      if (mnHeight < INF) {
        nodes[i].height = 1 + mnHeight;
        --i;
      }
      // for (int j = 1; j <= nExt; ++j) {
      //   cout << nodes[j].excess << ' ' << nodes[j].height << '\n';
      // }
      // cout << '\n';
    }
    if (finish) {
      break;
    }
  }
  int sol = 0;
  for (int i = 1; i <= nExt; ++i) {
    if (g[i][n]) {
      sol += flow[i][n];
    }
  }
  fout << sol << '\n';

  return;
}

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

  return 0;
}