#include <iostream>
#include <vector>
#include <list>
#include <queue>
unsigned long *data;
int n, m;
std::list<unsigned int> get_path(){
unsigned int visited[n + 1];
for(int i = 0; i <= n; i++)
visited[i] = 0;
visited[1] = 1;
std::queue<unsigned int> queue({1});
while(!queue.empty()){
unsigned int v = queue.front();
queue.pop();
if(data[v * (n + 1) + n] > 0){
visited[n] = v;
break;
}
for(int i = 1; i <= n; i++){
if(visited[i] == 0 && data[v * (n + 1) + i] > 0){
visited[i] = v;
queue.push(i);
}
}
}
std::list<unsigned int> result = {};
if(visited[n] != 0){
result.push_front (n);
unsigned int last = n;
while(last != 1){
last = visited[last];
result.push_front (last);
}
}
return result;
}
unsigned long get_path_throughput(std::list<unsigned int> path){
unsigned long result = ULONG_MAX;
std::list<unsigned int>::iterator it = path.begin();
unsigned int v1 = *it;
it++;
for(; it != path.end(); ++it) {
unsigned long val = data[v1 * (n + 1) + *it];
if(val < result){
result = val;
}
v1 = *it;
}
return result;
}
void process_path(std::list<unsigned int> path, unsigned long throughput){
std::list<unsigned int>::iterator it = path.begin();
unsigned int v1 = *it;
it++;
for(; it != path.end(); ++it){
//std::cout << v1 << "," << *it << std::endl;
data[v1 * (n + 1) + *it] -= throughput;
data[*it * (n + 1) + v1] += throughput;
v1 = *it;
}
}
int main(int argc, const char * argv[]) {
std::cin >> n >> m;
//std::cout << "n=" << n << " m=" << m << "\n";
data = (unsigned long *)malloc((n + 1) * (n + 1) * sizeof(unsigned long));
unsigned int a, b;
unsigned long c;
for(int i = 0; i <= n; i++){
for(int j = 0; j <= n; j++){
data[i * (n + 1) + j] = 0;
}
}
for(int i = 0; i < m; i++){
std::cin >> a >> b >> c;
//std::cout << "a=" << a << " b=" << b << " c=" << c << "\n";
data[a * (n + 1) + b] = c;
}
/*
for(int i = 0; i < n + 1; i++){
for(int j = 0; j < n + 1; j++){
std::cout << data[i * (n + 1) + j] << "\t";
}
std::cout << "\n";
}
std::cout << "\n";
*/
std::list<unsigned int> mypath;
unsigned long total_throughput = 0;
do{
mypath = get_path();
/*
std::cout << "path \n";
for (std::list<unsigned int>::const_iterator i = mypath.begin(); i != mypath.end(); ++i)
std::cout << *i << ' ';
std::cout << "\n";
*/
if(!mypath.empty()){
unsigned long throughput = get_path_throughput(mypath);
total_throughput += throughput;
//std::cout << "throughput " << throughput << std::endl;
process_path(mypath, throughput);
/*
for(int i = 0; i < n + 1; i++){
for(int j = 0; j < n + 1; j++){
std::cout << data[i * (n + 1) + j] << "\t";
}
std::cout << "\n";
}
std::cout << "\n";
*/
}
} while (!mypath.empty());
std::cout << total_throughput << "\n";
return 0;
}