#include<bits/stdc++.h>
using namespace std;
int const NMax = 2505, oo = 1000000000;
vector <pair<int, int> > G[NMax];
int n, m, maxflow, source, target;
int pred[NMax], D[NMax];
queue <int> q;
void Read()
{
int i, x, y, c;
scanf("%d %d", &n, &m);
for(i = 0; i < m; i++){
scanf("%d %d %d", &x, &y, &c);
if(x != y){
G[x].push_back(make_pair(y, c));
G[y].push_back(make_pair(x, 0));
}
}
source = 1;
target = n;
}
int findIndex(int node, int neigh)
{
for(int i = 0; i < G[node].size(); i++)
if(G[node][i].first == neigh and G[node][i].second > 0)
return i;
return -1;
}
int findIndexNull(int node, int neigh)
{
for(int i = 0; i < G[node].size(); i++)
if(G[node][i].first == neigh)
return i;
return -1;
}
bool Bell()
{
int i, node;
q.push(source);
for(i = 0; i <= target; i++){
D[i] = oo;
pred[i] = 0;
}
D[source] = 0;
while(q.size()){
node = q.front();
q.pop();
for(auto it : G[node])
if(D[it.first] == oo and it.second > 0){
D[it.first] = D[node] + 1;
pred[it.first] = node;
q.push(it.first);
}
}
return D[target] != oo;
}
void Flow()
{
int flow, ind, node, fromIndex, toIndex;
while(Bell()){
for(auto it : G[target]){
pred[target] = it.first;
flow = oo;
node = target;
while(1 < node){
ind = findIndex(pred[node], node);
if(ind == -1){
flow = 0;
break;
}
flow = min(flow, G[pred[node]][ind].second);
node = pred[node];
}
maxflow += flow;
node = target;
while(node > 1){
fromIndex = findIndex(pred[node], node);
toIndex = findIndexNull(node, pred[node]);
G[pred[node]][fromIndex].second -= flow;
G[node][toIndex].second += flow;
node = pred[node];
}
}
}
printf("%d\n", maxflow);
}
int main()
{
freopen("maxflow.in", "r", stdin);
freopen("maxflow.out", "w", stdout);
Read();
Flow();
return 0;
}