// O(E * |f|)
#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);
}

constexpr static int INF = 1e9;

optional<pair<vector<int>, int>> bfs(int start, int n, int nExt, vector<vector<int>>& flow, vector<vector<int>>& g)
{
    queue<pair<int, int>> q;
    vector<int> parents(nExt + 1, -1);
    q.push({start, INF});
    while (!q.empty())
    {
        auto [node, val] = q.front();
        q.pop();
        if (node == n)
        {
            return optional<pair<vector<int>, int>>(make_pair(parents, val));
        }
        for (int i = 2; i <= nExt; ++i)
        {
            if (g[node][i] && flow[node][i] < g[node][i] && parents[i] == -1)
            {
                parents[i] = node;
                q.push({i, min(val, g[node][i] - flow[node][i])});
            }
            if (g[i][node] && flow[i][node] && parents[i] == -1)
            {
                parents[i] = node;
                q.push({i, min(val, flow[i][node])});
            }
        }
    }

    return {};
}

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));
    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;
    vector<vector<int>> flow(nExt + 1, vector<int>(nExt + 1, 0));
		do
		{
			auto ret = bfs(1, n, nExt, flow, gExt);
			if (!ret.has_value())
			{
				break;
			}
			auto [parents, val] = ret.value();
			int node = n;
			while (1)
			{
				int parent = parents[node];
				if (parent == -1)
				{
					break;
				}
				if (gExt[parent][node])
				{
					flow[parent][node] += val;
				}
				else
				{
					flow[node][parent] -= val;
				}
				node = parent;
			}
		}
    while (1);
    fout << accumulate(flow[1].begin(), flow[1].end(), 0) << '\n';

    return;
}

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

    return 0;
}