#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 discharge(auto& it, auto& nodes, auto& gAdj, auto& g, auto& flow);

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;
  list<int> l;
  for (int i = 2; i <= nExt; ++i) {
    if (i == n) {
      continue;
    }
    l.push_back(i);
  }
  for (list<int>::iterator it = l.begin(); it != l.end(); ) {
    int node = *it;
    int old_height = nodes[node].height;
    discharge(it, nodes, gAdj, gExt, flow);
    if (nodes[node].height > old_height) {
      l.push_front(node);
      l.erase(it);
      it = l.begin();
    } else {
      advance(it, 1);
    }
  }
  int sol = 0;
  for (int i = 1; i <= nExt; ++i) {
    if (gExt[i][n]) {
      sol += flow[i][n];
    }
  }
  fout << sol << '\n';

  return;
}

void relabel(int node, auto& nodes, auto& gAdj, auto& g, auto& flow) {
  int mnHeight = 1e9;
  for (auto neigh : gAdj[node]) {
    if (g[node][neigh] - flow[node][neigh] > 0 || (g[neigh][node] && flow[neigh][node])) {
      mnHeight = min(mnHeight, nodes[neigh].height);
    }
  }
  if (mnHeight != 1e9) {
    nodes[node].height = 1 + mnHeight;
  }
}

void discharge(auto& it, auto& nodes, auto& gAdj, auto& g, auto& flow) {
  int node = *it;
  while (nodes[node].excess) {
    for (auto neigh : gAdj[node]) {
      if (nodes[node].height != nodes[neigh].height + 1) {
        continue;
      }
      if (g[node][neigh] && flow[node][neigh] < g[node][neigh]) {
        int mn = min(g[node][neigh] - flow[node][neigh], nodes[node].excess);
        flow[node][neigh] += mn;
        nodes[node].excess -= mn;
        nodes[neigh].excess += mn;
      } else if (g[neigh][node] && flow[neigh][node]) {
        int mn = min(flow[neigh][node], nodes[node].excess);
        flow[neigh][node] -= mn;
        nodes[node].excess -= mn;
        nodes[neigh].excess += mn;
      }
    }
    if (nodes[node].excess) {
      relabel(node, nodes, gAdj, g, flow);
    }
  }
}

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

  return 0;
}