//.h file code:
#include <string>
#include <vector>
#include <algorithm>
#include <iostream>
#include <limits>
class Task2
{
static void main(std::vector<std::wstring> &args);
public:
static std::vector<std::vector<long long>> switch_edges(std::vector<std::vector<long long>> &am, std::vector<int> &path, long long flow);
static long long flow_of_path(std::vector<std::vector<long long>> &am, std::vector<int> &path);
static std::vector<int> find_path(std::vector<std::vector<long long>> &am, int source, int target, std::vector<int> &visited, std::vector<int> &track);
static void printam(std::vector<std::vector<int>> &am);
};
//----------------------------------------------------------------------------------------
// Copyright © 2007 - 2018 Tangible Software Solutions, Inc.
// This class can be used by anyone provided that the copyright notice remains intact.
//
// This class includes methods to convert multidimensional arrays to C++ vectors.
//----------------------------------------------------------------------------------------
class RectangularVectors
{
public:
static std::vector<std::vector<long long>> ReturnRectangularTangibleTemplonglongVector(int size1, int size2)
{
std::vector<std::vector<long long>> newVector(size1);
for (int vector1 = 0; vector1 < size1; vector1++)
{
newVector[vector1] = std::vector<long long>(size2);
}
return newVector;
}
};
//.cpp file code:
void Task2::main(std::vector<std::wstring> &args)
{
Scanner *s = new Scanner(System::in);
int n = s->nextInt();
int m = s->nextInt();
//JAVA TO C++ CONVERTER NOTE: The following call to the 'RectangularVectors' helper class reproduces the rectangular array initialization that is automatic in Java:
//ORIGINAL LINE: long[][] am = new long [n+1][n+1];
std::vector<std::vector<long long>> am = RectangularVectors::ReturnRectangularTangibleTemplonglongVector(n + 1, n + 1);
long long flow = 0;
for (int i = 0; i < m; i++)
{
int x = s->nextInt();
int y = s->nextInt();
am[x][y] = s->nextInt();
}
double path_sum_timer = 0;
std::vector<int> visited;
std::vector<int> track;
std::vector<int> path = find_path(am, 1, n, visited, track);
visited = std::vector<int>();
track = std::vector<int>();
while (path.size() != 0)
{
long long tmp_flow = flow_of_path(am, path);
flow += tmp_flow;
am = switch_edges(am,path, tmp_flow);
path = find_path(am, 1, n, visited, track);
visited = std::vector<int>();
track = std::vector<int>();
}
std::wcout << flow << std::endl;
}
std::vector<std::vector<long long>> Task2::switch_edges(std::vector<std::vector<long long>> &am, std::vector<int> &path, long long flow)
{
for (int i = 0; i < path.size() - 1; i++)
{
int x = path[i];
int y = path[i + 1];
am[x][y] = am[x][y] - flow;
am[y][x] += flow;
}
return am;
}
long long Task2::flow_of_path(std::vector<std::vector<long long>> &am, std::vector<int> &path)
{
long long flow = std::numeric_limits<long long>::max();
for (int i = 0; i < path.size() - 1; i++)
{
int x = path[i];
int y = path[i + 1];
if (am[x][y] < flow)
{
flow = am[x][y];
}
}
return flow;
}
std::vector<int> Task2::find_path(std::vector<std::vector<long long>> &am, int source, int target, std::vector<int> &visited, std::vector<int> &track)
{
visited.push_back(source);
for (int i = 1; i < am[source].size(); i++)
{
if (am[source][i] != 0 && !std::find(visited.begin(), visited.end(), i) != visited.end())
{
if (i == target)
{
track.push_back(0, target);
track.push_back(0, source);
return track;
}
else
{
std::vector<int> track_from_i = find_path(am, i, target, visited, track);
if (std::find(track_from_i.begin(), track_from_i.end(), target) != track_from_i.end())
{
track.push_back(0, source);
return track;
}
}
}
}
return (std::vector<int>());
}
void Task2::printam(std::vector<std::vector<int>> &am)
{
for (int i = 0; i < am.size(); i++)
{
for (int j = 0; j < am[i].size(); j++)
{
std::wcout << am[i][j];
}
std::wcout << L"" << std::endl;
}
}
