#include <iostream>
#include <cstdio>
#include <vector>
#define NMAX 1000
#define MMAX 5000
#define INF 550000000
using namespace std;
struct muchie {
int nod1, nod2, flux, cap;
muchie(int nnod1 = 0, int nnod2 = 0, int fflux = 0, int ccap = 0) {
nod1 = nnod1, nod2 = nnod2, flux = fflux, cap = ccap;
}
};
bool dest;
int n, m, flux_tot, flux;
int inv[2 * MMAX + 5], from[NMAX + 5], mincf[NMAX + 5];
muchie muchii[2 * MMAX + 5];
vector<int> v[NMAX + 5];
void update_flux(int nod, int flux) {
if(nod == 1)
return;
muchie &mfr = muchii[from[nod]], &imfr = muchii[inv[from[nod]]];
update_flux(mfr.nod1, flux);
mfr.flux += flux;
imfr.flux -= flux;
mincf[nod] = min(mfr.cap - mfr.flux, mincf[mfr.nod1]);
}
void dfs(int nod) {
muchie mfr = muchii[from[nod]], imfr = muchii[inv[from[nod]]];
mincf[nod] = min(mfr.cap - mfr.flux, mincf[mfr.nod1]);
if(nod == n) {
flux_tot += mincf[n];
update_flux(n, mincf[n]);
from[n] = 0;
dest = true;
return;
}
for(int x: v[nod]) {
mfr = muchii[x], imfr = muchii[inv[x]];
if(mfr.cap - mfr.flux == 0 || from[mfr.nod2])
continue;
from[mfr.nod2] = x;
dfs(mfr.nod2);
}
}
int main() {
freopen("maxflow.in", "r", stdin);
freopen("maxflow.out", "w", stdout);
int a, b, c;
scanf("%d %d", &n, &m);
for(int i = 1; i <= m; i++) {
scanf("%d %d %d", &a, &b, &c);
muchii[i] = muchie(a, b, 0, c);
v[a].push_back(i);
}
for(int i = 1; i <= m; i++)
if(!inv[i]) {
for(int j = i + 1; j <= m; j++)
if(!inv[j] && muchii[i].nod1 == muchii[j].nod2 && muchii[i].nod2 == muchii[j].nod1) {
inv[i] = j;
inv[j] = i;
break;
}
if(!inv[i]) {
muchii[++m] = muchie(muchii[i].nod2, muchii[i].nod1, 0, 0);
inv[i] = m;
inv[m] = i;
v[muchii[i].nod2].push_back(m);
}
}
flux = 1;
mincf[0] = INF + 5;
dest = true;
muchii[0] = muchie(0, 0, 0, INF + 5);
while(dest) {
for(int i = 1; i <= n; i++)
from[i] = 0;
dest = false;
dfs(1);
}
// for(int i = 1; i <= n; i++)
// for(muchie vec: v[i])
// printf("muchia (%d, %d) are flux %d/%d\n", i, vec.nod, vec.flux, vec.cap);
printf("%d", flux_tot);
return 0;
}