#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;
const int NN = 1024;
int cap[NN][NN], viz[NN], pred[NN];
vector<int> vec[NN];
void BFS(int nod){
if (!viz[nod]){
//printf("%d ", nod);
viz[nod] = 1;
for(int i = 0; i < vec[nod].size(); i++){
if (cap[nod][vec[nod][i]] && pred[vec[nod][i]] == -1)
pred[vec[nod][i]] = nod,
BFS(vec[nod][i]);
}
}
}
int dinic(int n, int s, int t) {
int /*q[NN], pred[NN],*/ flow = 0;
while ( 1 ) {
memset(pred, -1, sizeof(pred));
memset(viz, 0, sizeof(viz));
/*int qf = 0, qb = 0;
q[qb++] = s;
pred[s] = -2;
while (qb > qf && pred[t] == -1)
for (int u = q[qf++], i = 0, v; i < vec[u].size(); i++) {
v = vec[u][i];
if (pred[vec[u][i]] == -1 && cap[u][v])
q[qb++] = v, pred[v] = u;
}
printf("\nq: ");
for(int i = 0; i < qb; i++)
printf("%d ", q[i]);*/
pred[s] = -2;
BFS(1);
/*printf("\npred: ");
for(int i = 1; i <= n; i++)
printf("%d ", pred[i]);*/
if (pred[t] == -1) break;
for (int z = 1; z <= n; z++)
if (cap[z][t] && pred[z] != -1) {
int capmin = cap[z][t];
for (int v = z, u = pred[v]; u >= 0; v = u, u = pred[v])
capmin = min(capmin, cap[u][v]);
if (!capmin) continue;
cap[z][t] -= capmin, cap[t][z] += capmin;
for (int v = z, u = pred[v]; u >= 0; v = u, u = pred[v])
cap[u][v] -= capmin, cap[v][u] += capmin;
flow += capmin;
}
}
return flow;
}
int main() {
FILE *in = fopen("maxflow.in", "r"), *out = fopen("maxflow.out", "w");
if (in && out){
int n, s, t, m, u, v, c;
fscanf(in, "%d %d", &n, &m);
s = 1, t = n;
for(int i = 0; i < m; i++) {
fscanf(in, "%d %d %d", &u, &v, &c);
cap[u][v] += c;
vec[u].push_back(v);
vec[v].push_back(u);
}
//BFS(1);
//printf("\n\n");
//for(int i = 1; i <= n; i++) printf("%d ", pred[i]);
fprintf(out, "%d\n", dinic(n, s, t));
fclose(in), fclose(out);
}
return 0;
}