#include <bits/stdc++.h>
// #pragma optimize ("O3")
// #pragma optimize("unroll-loops,fast-math")
// #pragma target ("avx2,bmi2,popcnt,lzcnt")

#define int long long
#define pii pair<int, int>
#define fs first
#define sd second

using namespace std;

const string fileName = "maxflow";
ifstream in(fileName + ".in");
ofstream out(fileName + ".out");

int n, m, u, v, c;
int capacity[1005][1005];
int parent[1005];
vector<int> adjacency[1005];

int bfs(int source, int sink) {
    for(int i = 1; i <= n; i++)
        parent[i] = -1;
    parent[source] = -2;
    queue<pii> q;
    q.push({source, 1e12});
    while(!q.empty()) {
        int node = q.front().fs;
        int flow = q.front().sd;
        q.pop();
        for(auto nxt : adjacency[node]) {
            if(parent[nxt] == -1 && capacity[node][nxt]) {
                parent[nxt] = node;
                int new_flow = min(flow, capacity[node][nxt]);
                if(nxt == sink)
                    return new_flow;
                q.push({nxt, new_flow});
            }
        }
    }
    return 0;
}

int maxflow(int source, int sink) {
    int flow = 0;
    int new_flow;
    while(new_flow = bfs(source, sink)) {
        flow += new_flow;
        int crt = sink;
        while(crt != source) {
            int prev = parent[crt];
            capacity[prev][crt] -= new_flow;
            capacity[crt][prev] += new_flow;
            crt = prev;
        }
    }
    return flow;
}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    in.tie(NULL); out.tie(NULL);

    in >> n >> m;
    for(int i = 1; i <= m; i++) {
        in >> u >> v >> c;
        adjacency[u].push_back(v);
        adjacency[v].push_back(u);
        capacity[u][v] = c;
    }
    cout << 1 << '\n';
    out << maxflow(1, n) << '\n';

    return 0;
}