#include <bits/stdc++.h>
using namespace std;
ifstream f("maxflow.in");
ofstream g("maxflow.out");
int capacitate_flux[10][10];
int flowPassed[10][10];
vector<int> graf[10];
int parList[10];
int currentPathC[10];
int bfs(int start, int end)//breadth first search
{
memset(parList, -1, sizeof(parList));
memset(currentPathC, 0, sizeof(currentPathC));
queue<int> q;//declare queue vector
q.push(start);
parList[start] = -1;//initialize parlist’s source node
currentPathC[start] = 999;//initialize currentpath’s source node
while(!q.empty())// if q is not empty
{
int nod_curent = q.front();
q.pop();
for(int i=0; i < graf[nod_curent].size(); i++)
{
int to = graf[nod_curent][i];
if(parList[to] == -1)
{
if(capacitate_flux[nod_curent][to] - flowPassed[nod_curent][to] > 0)
{
parList[to] = nod_curent;
currentPathC[to] = min(currentPathC[nod_curent], capacitate_flux[nod_curent][to] - flowPassed[nod_curent][to]);
if(to == end)
{
return currentPathC[end];
}
q.push(to);
}
}
}
}
return 0;
}
int edmondsKarp(int start, int end)
{
int maxFlow = 0;
while(true)
{
int flow = bfs(start, end);
if (flow == 0)
{
break;
}
maxFlow += flow;
int nod_curent = end;
while(nod_curent != start)
{
int nod_anterior = parList[nod_curent];
flowPassed[nod_anterior][nod_curent] += flow;
flowPassed[nod_curent][nod_anterior] -= flow;
nod_curent = nod_anterior;
}
}
return maxFlow;
}
int main()
{
int N, M;
// cout<<"enter the number of nodes and edges\n";
f >> N >> M;
int source=1, dest=N;
for(int ed = 0; ed < M; ed++)
{
// cout<<"enter the start and end vertex along with capacity\n";
int from, to, cap;
f>>from>>to>>cap;
capacitate_flux[from][to] = cap;
graf[from].push_back(to);
graf[to].push_back(from);
}
int maxFlow = edmondsKarp(source, dest);
g<<maxFlow<<endl;
}
//
//#include <bits/stdc++.h>
//using namespace std;
//
////ifstream f("maxflow.in");
////ofstream graf("maxflow.out");
//
//int capacity[1001][1001],n,m,flow,max_flow;
//vector<int> visited,parent;
//vector<vector<int>> v;
//
//bool bfs()
//{
// fill(visited.begin(), visited.end(), 0);
// fill(parent.begin(), parent.end(), 0);
//
// visited[1] = 1;
// parent[1] = 1;
// queue<int> q;
// q.push(1);
//
// while(!q.empty())
// {
// int nod = q.front();
//
// q.pop();
//
// if(nod == n)
// return true;
//
// for(int i=0; i<v[nod].size(); i++)
// {
// if(!visited[v[nod][i]] && capacity[nod][v[nod][i]] > 0)
// {
// q.push(v[nod][i]);
// parent[v[nod][i]] = nod;
// visited[v[nod][i]] = 1;
// }
// }
// }
//
// return false;
//
//
//}
//
//int main()
//{
// int a,b,capacitate_flux;
// cin>>n>>m;
// visited.resize(n+2, 0);
// parent.resize(n+2, 0);
// v.resize(n+2, {});
//
// for(int i=1; i<=m; i++)
// {
// cin>>b>>capacitate_flux>>a;
// v[b].push_back(capacitate_flux);
// v[capacitate_flux].push_back(b);
// capacity[b][capacitate_flux] = a;
// }
//
//// int reusit = bfs();
//
// while(bfs())
// {
// for(int i=0; i<v[n].size(); i++)
// {
// if(visited[v[n][i]])
// {
// parent[n] = v[n][i];
// flow = INT_MAX;
// for(int j=n; j!=1; j=parent[j])
// {
// flow=min(flow, capacity[parent[j]][j]);
// }
// if(flow != 0)
// {
// for(int j=n; j!=1; j=parent[j])
// {
// capacity[parent[j]][j] -= flow;
// capacity[j][parent[j]] += flow;
// }
// max_flow += flow;
// }
// }
// }
// reusit = bfs();
// }
// cout<<max_flow;
// return 0;
//}
//
//
//
//
//
//
//
////
////#include <iostream>
////#include <bits/stdc++.h>
////using namespace std;
//////#define V 100
////
////int N;
////int graph[1001][1001];
////int rGraph[1001][1001];
//////int V;
////
/////* Returns true if there is a path from source 's' to sink 't' in
//// * residual graph. Also fills parent[] to store the path */
////bool BFs( int s, int t, int parent[])
////{
//// // Create a visited array and mark all vertices as not visited
//// bool visited[1001];
//// memset(visited, 0, sizeof(visited));
//// // Create a queue, enqueue source vertex and mark source vertex
//// // as visited
//// queue <int> q;
//// q.push(s);
//// visited[s] = true;
//// parent[s] = -1;
//// // Standard BFS Loop
//// while (!q.empty())
//// {
//// int u = q.front();
//// q.pop();
//// for (int v = 0; v < N; v++)
//// if (visited[v] == false && rGraph[u][v] > 0)
//// {
//// q.push(v);
//// parent[v] = u;
//// visited[v] = true;
//// }
//// }
//// // If we reached sink in BFS starting from source, then return
//// // true, else false
//// return visited[t] == true;
////}
////// Returns tne maximum flow from s to t in the given graph
////int fordFulkerson( int s, int t, int N)
////{
//// int u, v;
//// // Create a residual graph and fill the residual graph with
//// // given capacities in the original graph as residual capacities
//// // in residual graph
//// int rGraph[N][N]; // Residual graph where rGraph[i][j] indicates
//// // residual capacity of edge from i to j (if there
//// // is an edge. If rGraph[i][j] is 0, then there is not)
//// for (u = 0; u < N; u++)
//// for (v = 0; v < N; v++)
//// rGraph[u][v] = graph[u][v];
//// int parent[N]; // This array is filled by BFS and to store path
//// int max_flow = 0; // There is no flow initially
//// // Augment the flow while tere is path from source to sink
//// while (BFs( s, t, parent))
//// {
//// // Find minimum residual capacity of the edges along the
//// // path filled by BFS. Or we can say find the maximum flow
//// // through the path found.
//// int path_flow = INT_MAX;
//// for (v = t; v != s; v = parent[v])
//// {
//// u = parent[v];
//// path_flow = min(path_flow, rGraph[u][v]);
//// }
//// // update residual capacities of the edges and reverse edges
//// // along the path
//// for (v = t; v != s; v = parent[v])
//// {
//// u = parent[v];
//// rGraph[u][v] -= path_flow;
//// rGraph[v][u] += path_flow;
//// }
//// // Add path flow to overall flow
//// max_flow += path_flow;
//// }
//// // Return the overall flow
//// return max_flow;
////}
////
////int main(){
//// int M, x, y, z;
//// int Flux_max;
////
////
//// cin>>N>>M; // noduri, muchii
//// int graf[N][N];
////
//// for(int i=1;i<=N;i++)
//// for(int j=1;j<=N;j++)
//// graf[i][j]=0;
////
//// for(int i=0;i<M;i++){
//// cin>>x>>y>>z;
//// graf[x][y]=z;
//// }
////
//// for(int i=1;i<=N;i++){
//// for(int j=1;j<=N;j++)
//// cout<<graf[i][j]<<" ";
//// cout<<endl;}
////
//// // 1 sursa, N destinatia
//// Flux_max= fordFulkerson(1,N,N);
//// cout<<Flux_max;
////
////}
////