Given a graph which represents a flow network with N vertices numbered 1 to N and M edges.Find the maximum flow from vertex numbered 1 to vertex numbered N.
In a flow network,every edge has a flow capacity and the maximum flow of a path can't exceed the flow-capacity of an edge in the path.
Example 1:
Input:
N = 5, M =  4
Edges[]= {{1,2,1},{3,2,2},{4,2,3},{2,5,5}}
Output: 1 
Explanation: 
1 - 2 - 3
   / \
  4   5 
1 unit can flow from 1 -> 2 - >5 
 
Example 2:
Input:
N = 4, M = 4
Edges[] = {{1,2,8},{1,3,10},{4,2,2},{3,4,3}}
Output: 5 
Explanation:
  1 - 2 
  |   |
  3 - 4
3 unit can flow from 1 -> 3 -> 4
2 unit can flow from 1 -> 2 -> 4
Total max flow from 1 to N = 3+2=5
Your Task: 
You don't need to read input or print anything. Your task is to complete the function solve() which takes the N (the number of vertices) ,M (the number of Edges) and the array Edges[] (Where Edges[i] denoting an undirected edge between Edges[i][0] and Edges[i][1] with a flow capacity of Edges[i][2]), and returns the integer denoting the maximum flow from 1 to N.
Expected Time Complexity: O(max_flow*M)
Expected Auxiliary Space: O(N+M)
Where max_flow is the maximum flow from 1 to N
Constraints:
1 <= N,M,Edges[i][2] <= 1000
1 <= Edges[i][0],Edges[i][1] <= N

Difficulty: MEDIUM_HARD
Tags: Graph algorithms

Data structures
Skill types: Data structures
Expected Time Complexity: O(max_flow*M)
Expected Auxiliary Space: O(N+M)

Starter code:
#User function Template for python3

class Solution:

    def findMaxFlow(self, N, M, Edges): 

        #code here

Solutions:
from collections import deque

class Edge:

	def __init__(self, v, w, c):
		self.v = v
		self.w = w
		self.cap = c
		self.flow = 0

	def other(self, v):
		return self.w if v == self.v else self.v

class Solution:

	def bfs(self, s, t, parent):
		q = deque()
		parent[s] = -2
		q.append((s, 100000))
		while len(q) > 0:
			(v, flow) = q.popleft()
			for w in self.adj[v]:
				if parent[w] == -1 and self.capacity[v][w] > 0:
					parent[w] = v
					nflow = min(flow, self.capacity[v][w])
					if w == t:
						return nflow
					q.append((w, nflow))
		return 0

	def findMaxFlow(self, N, M, Edges):
		self.adj = [[] for i in range(N)]
		self.capacity = [[0 for _ in range(N)] for _ in range(N)]
		for e in Edges:
			self.adj[e[0] - 1].append(e[1] - 1)
			self.adj[e[1] - 1].append(e[0] - 1)
			self.capacity[e[0] - 1][e[1] - 1] += e[2]
			self.capacity[e[1] - 1][e[0] - 1] += e[2]
		flow = 0
		while True:
			parent = [-1] * N
			new_flow = self.bfs(0, N - 1, parent)
			if new_flow == 0:
				break
			flow += new_flow
			curr = N - 1
			while curr != 0:
				prev = parent[curr]
				self.capacity[prev][curr] -= new_flow
				self.capacity[curr][prev] += new_flow
				curr = prev
		return flow


class Solution:

	def findMaxFlow(self, N, M, Edges):
		graph = [[0] * N for _ in range(N)]
		for (frm, to, flow) in Edges:
			graph[frm - 1][to - 1] += flow
			graph[to - 1][frm - 1] += flow

		def bfs(s, t, parent):
			q = [(s, float('inf'))]
			while q:
				(cur, flow) = q.pop(0)
				for (nxt, capacity) in enumerate(graph[cur]):
					if parent[nxt] is None and capacity > 0:
						parent[nxt] = cur
						new_flow = min(flow, capacity)
						if nxt == t:
							return new_flow
						q.append((nxt, new_flow))
			return 0

		def maxflow(s, t):
			flow = 0
			while True:
				parent = [None] * N
				parent[s] = -1
				new_flow = bfs(s, t, parent)
				if new_flow == 0:
					break
				flow += new_flow
				cur = t
				while cur != s:
					prev = parent[cur]
					graph[prev][cur] -= new_flow
					graph[cur][prev] += new_flow
					cur = prev
			return flow
		return maxflow(0, N - 1)


from queue import Queue

class Solution:

	def findMaxFlow(self, N, M, Edges):
		adj = [[] for _ in range(N + 1)]
		for e in Edges:
			adj[e[0]].append(e)
			adj[e[1]].append(e)
		max_flow = 0
		while True:
			visited_list = ['w' for _ in range(N + 1)]
			visited_list[1] = 'g'
			to_check_que = Queue()
			to_check_que.put_nowait(1)
			N_path = self.bfsOfGraph(N, adj, visited_list, to_check_que)
			if N_path is None:
				break
			max_flow += N_path[1][N]
			for e in N_path[0][N]:
				e[2] -= N_path[1][N]
		return max_flow

	def bfsOfGraph(self, N, adj, visited_list, to_check_que):
		branch_path = [[[] for _ in range(N + 1)], [float('inf') for _ in range(N + 1)]]
		found_N = False
		while not to_check_que.empty() and (not found_N):
			check_vert = to_check_que.get_nowait()
			if len(adj[check_vert]) > 0:
				for s in adj[check_vert]:
					desti = s[1]
					if check_vert == desti:
						desti = s[0]
					if visited_list[desti] == 'w' and s[2] > 0:
						to_check_que.put_nowait(desti)
						visited_list[desti] = 'g'
						branch_path[0][desti].extend(branch_path[0][check_vert])
						branch_path[0][desti].append(s)
						if branch_path[1][check_vert] < s[2]:
							branch_path[1][desti] = branch_path[1][check_vert]
						else:
							branch_path[1][desti] = s[2]
					if desti == N and visited_list[desti] == 'g':
						found_N = True
						break
			visited_list[check_vert] = 'b'
		if found_N:
			return branch_path
		else:
			return None


from collections import defaultdict

class Solution:

	def findMaxFlow(self, N, M, Edges):
		adjs = defaultdict(dict)
		for (s, d, c) in Edges:
			edge = adjs[s].get(d, None)
			if not edge:
				edge = [0, 0]
				adjs[s][d] = edge
				adjs[d][s] = edge
			edge[1] += c

		def _findPath(s, path, cap):
			vis[s] = True
			path.append(s)
			if s == N:
				return cap
			for (d, edge) in adjs[s].items():
				mul = 1 if s < d else -1
				if not vis[d] and edge[0] * mul != edge[1]:
					left = edge[1] - mul * edge[0]
					newcap = min(cap, left)
					used = _findPath(d, path, newcap)
					if used > 0:
						return used
			path.pop()
			return 0

		def _mod_path(path, used):
			np = len(path)
			for i in range(np - 1):
				(a, b) = (path[i], path[i + 1])
				edge = adjs[a][b]
				mul = 1 if a < b else -1
				edge[0] += mul * used
		ans = 0
		while True:
			(path, cap, vis) = ([], 10 ** 9, [False] * (N + 1))
			used = _findPath(1, path, cap)
			if used <= 0:
				break
			ans += used
			_mod_path(path, used)
		return ans


class Solution:

	def findMaxFlow(self, N, M, Edges):
		graph = []
		for _ in range(N + 1):
			graph.append([0] * (N + 1))
		for edge in Edges:
			graph[edge[0]][edge[1]] += edge[2]
			graph[edge[1]][edge[0]] += edge[2]
		max_flow = 0
		parent = [None] * (N + 1)
		while self.bfs(graph, N, parent):
			v = N
			flow = float('inf')
			while v != 1:
				flow = min(flow, graph[parent[v]][v])
				v = parent[v]
			max_flow += flow
			v = N
			while v != 1:
				graph[parent[v]][v] -= flow
				graph[v][parent[v]] += flow
				v = parent[v]
		return max_flow

	def bfs(self, graph, N, parent):
		Q = [1]
		is_visited = [False] * (N + 1)
		is_visited[1] = True
		while len(Q) != 0:
			u = Q.pop(0)
			for v in range(1, N + 1):
				w = graph[u][v]
				if is_visited[v] == False and w > 0:
					parent[v] = u
					is_visited[v] = True
					Q.append(v)
					if v == N:
						return True
		return False


class Solution:

	def findMaxFlow(self, N, M, Edges):
		adj = [[] for _ in range(N)]
		for (i, e) in enumerate(Edges):
			(f, t) = (e[0] - 1, e[1] - 1)
			(e[0], e[1]) = (f, t)
			adj[f].append(i)
			adj[t].append(i)
		F = [0] * M

		def find_augment_path():

			def path_to_source_target_path(path):
				(cur, st) = (N - 1, [])
				while cur != 0:
					eid = path[cur]
					(f, t) = (Edges[eid][0], Edges[eid][1])
					st.append(eid)
					cur = t if f == cur else f
				return list(reversed(st))
			(visited, path, q) = ([False] * N, [-1] * N, [0])
			visited[0] = True
			while q:
				qn = []
				for v in q:
					for eid in adj[v]:
						e = Edges[eid]
						(f, t, cap, flow) = (e[0], e[1], e[2], F[eid])
						if v == f and cap - flow > 0 and (not visited[t]):
							path[t] = eid
							if t == N - 1:
								return path_to_source_target_path(path)
							visited[t] = True
							qn.append(t)
						elif v == t and flow + cap > 0 and (not visited[f]):
							path[f] = eid
							if f == N - 1:
								return path_to_source_target_path(path)
							visited[f] = True
							qn.append(f)
				q = qn
			return []

		def fill_augment_path(path):
			(augment_flow, cur) = (1000 * 2, 0)
			for eid in path:
				e = Edges[eid]
				(f, t, cap, flow) = (e[0], e[1], e[2], F[eid])
				if f == cur:
					augment_flow = min(augment_flow, cap - flow)
					cur = t
				else:
					augment_flow = min(augment_flow, flow + cap)
					cur = f
			cur = 0
			for eid in path:
				e = Edges[eid]
				(f, t, cap) = (e[0], e[1], e[2])
				if f == cur:
					F[eid] += augment_flow
					cur = t
				else:
					F[eid] -= augment_flow
					cur = f
			return augment_flow
		res = 0
		while True:
			path = find_augment_path()
			if not path:
				break
			res += fill_augment_path(path)
		return res


def MaxFlow(edges, n):
	G = [[0 for i in range(n + 1)] for j in range(n + 1)]
	for i in edges:
		(u, v, w) = (i[0], i[1], i[2])
		G[u][v] += w
		G[v][u] += w
	return FordFulkerson(G, n)

def BFS(G, n, parent):
	visited = [0] * (n + 1)
	q = [1]
	visited[1] = 1
	while len(q):
		u = q.pop()
		for v in range(1, n + 1):
			if visited[v] == False and G[u][v] > 0:
				visited[v] = True
				q.insert(0, v)
				parent[v] = u
				if v == n:
					return True
	return False

def FordFulkerson(G, n):
	parent = [-1] * (n + 1)
	max_flow = 0
	while BFS(G, n, parent):
		min_cap = float('inf')
		s = n
		while s != 1:
			min_cap = min(min_cap, G[parent[s]][s])
			s = parent[s]
		max_flow += min_cap
		v = n
		while v != 1:
			u = parent[v]
			G[u][v] -= min_cap
			G[v][u] += min_cap
			v = parent[v]
	return max_flow

class Solution:

	def findMaxFlow(self, N, M, Edges):
		return MaxFlow(Edges, N)


from collections import defaultdict as dt
from math import inf

class Solution:

	def findMaxFlow(self, n, m, Edges):
		mi = inf
		found = False
		par = [-1 for i in range(n + 1)]

		def f(i, mi=inf):
			nonlocal found
			if found:
				return
			if i == n:
				nonlocal maxflow
				found = True
				j = i
				while j != 1:
					x[par[j], j] -= mi
					x[j, par[j]] += mi
					j = par[j]
				maxflow += mi
				return
			for j in nodes[i]:
				if found:
					return
				if v[j] == 0:
					if x[i, j] != 0:
						v[j] = 1
						par[j] = i
						f(j, min(mi, x[i, j]))
						v[j] = 0
						if found == False:
							x[i, j] = 0
							x[j, i] = 0
		nodes = dt(set)
		x = dt(int)
		for (a, b, c) in Edges:
			nodes[a].add(b)
			nodes[b].add(a)
			x[a, b] += c
			x[b, a] += c
		v = [0 for i in range(n + 1)]
		maxflow = 0
		while True:
			found = False
			v[1] = 1
			f(1)
			if not found:
				break
		return maxflow


from collections import defaultdict, deque

class Solution:

	def findMaxFlow(self, N, M, Edges):
		(n, m) = (N, M)
		G = [[0 for j in range(n + 1)] for i in range(n + 1)]
		E = defaultdict(lambda : set())
		for (x, y, d) in Edges:
			G[x][y] += d
			G[y][x] += d
			E[x].add(y)
			E[y].add(x)
		Parent = [-1 for _ in range(n + 1)]

		def bfs(s, t, n):
			for i in range(n + 1):
				Parent[i] = -1
			q = deque([[float('inf'), s]])
			Parent[s] = -2
			while q:
				(f, x) = q.popleft()
				for adj in E[x]:
					if Parent[adj] == -1 and G[x][adj] > 0:
						Parent[adj] = x
						new_f = min(f, G[x][adj])
						if adj == t:
							return new_f
						q.append([new_f, adj])
			return 0
		flow = 0
		while True:
			n_flow = bfs(1, n, n)
			if n_flow == 0:
				break
			flow += n_flow
			curr = n
			while curr != 1:
				prev = Parent[curr]
				G[prev][curr] -= n_flow
				G[curr][prev] += n_flow
				curr = prev
		return flow


from collections import deque

class Solution:

	def bfs(self, source, sink, n):
		for i in range(len(self.parent)):
			self.parent[i] = -1
		vis = [False for i in range(n)]
		q = deque([source])
		min_cap = 1000000000.0
		vis[source] = True
		while q:
			u = q.popleft()
			for v in range(n):
				if not vis[v] and self.graph[u][v] != 0:
					vis[v] = True
					min_cap = min(min_cap, self.graph[u][v])
					self.parent[v] = u
					if v == sink:
						return min_cap
					q.append(v)
		return 0

	def ford_fulkerson(self, source, sink, n):
		self.parent = [-1 for i in range(n)]
		ans = 0
		while True:
			min_cap = self.bfs(source, sink, n)
			if min_cap == 0:
				break
			ans += min_cap
			v = sink
			while v != source:
				u = self.parent[v]
				self.graph[u][v] -= min_cap
				self.graph[v][u] += min_cap
				v = self.parent[v]
		return ans

	def findMaxFlow(self, n, m, Edges):
		self.graph = [[0 for i in range(n)] for i in range(n)]
		for (u, v, w) in Edges:
			u -= 1
			v -= 1
			self.graph[u][v] += w
			self.graph[v][u] += w
		return self.ford_fulkerson(0, n - 1, n)


from collections import defaultdict, deque

class Solution:

	def findMaxFlow(self, N, M, Edges):

		def bfs(s, d):
			vis = [0] * N
			q = deque()
			q.append(s)
			vis[s] = 1
			min_cap = float('inf')
			while q:
				u = q.popleft()
				for v in range(0, N):
					if vis[v] == 0 and g[u][v] > 0:
						if v == d:
							par[v] = u
							min_cap = min(min_cap, g[u][v])
							return min_cap
						q.append(v)
						vis[v] = 1
						min_cap = min(min_cap, g[u][v])
						par[v] = u
			return 0

		def fordFulkerson(s, d):
			ans = 0
			while bfs(s, d) != 0:
				min_cap = bfs(s, d)
				ans += min_cap
				v = d
				while v != s:
					u = par[v]
					g[u][v] -= min_cap
					g[v][u] += min_cap
					v = par[v]
			return ans
		g = [[0] * N for _ in range(N)]
		for (u, v, w) in Edges:
			g[u - 1][v - 1] += w
			g[v - 1][u - 1] += w
		par = [-1] * N
		return fordFulkerson(0, N - 1)


def bfs(source, sink, rGraph, parent, N):
	visited = [False] * N
	Q = [source]
	visited[source] = True
	parent[source] = 1
	while Q:
		u = Q.pop(0)
		for v in range(1, N):
			if not visited[v] and rGraph[u][v] > 0:
				visited[v] = True
				parent[v] = u
				Q.append(v)
				if v == sink:
					return True
	return False

class Solution:

	def findMaxFlow(self, N, M, Edges):
		source = 1
		sink = N
		N += 1
		rGraph = [[0] * N for i in range(N)]
		parent = [0] * N
		for (u, v, c) in Edges:
			rGraph[u][v] += c
			rGraph[v][u] += c
		mxflow = 0
		while bfs(source, sink, rGraph, parent, N):
			flow = 2 ** 31 - 1
			v = sink
			while v != source:
				u = parent[v]
				flow = min(flow, rGraph[u][v])
				v = u
			mxflow += flow
			v = sink
			while v != source:
				u = parent[v]
				rGraph[u][v] -= flow
				rGraph[v][u] += flow
				v = u
		return mxflow


from math import inf
from collections import deque

class Graph:

	def __init__(self, n, m, edges):
		self.nrows = len(edges)
		self.adjMat = [[0] * n for _ in range(n)]
		for (frm, to, flow) in edges:
			self.adjMat[frm - 1][to - 1] += flow
			self.adjMat[to - 1][frm - 1] += flow

class Solution:

	def bfs(self, n, m, s, t, parent, graph):
		visited = [False for _ in range(n)]
		adj = graph.adjMat
		q = deque()
		q.append(s)
		visited[s] = True
		parent[s] = None
		while q:
			u = q.popleft()
			for (v, cost) in enumerate(adj[u]):
				if not visited[v] and cost > 0:
					q.append(v)
					visited[v] = True
					parent[v] = u
		return True if visited[t] else False

	def findMaxFlow(self, n, m, edges):
		graph = Graph(n, m, edges)
		adjMat = graph.adjMat
		parent = [None for _ in range(n)]
		max_flow = 0
		source = 0
		sink = n - 1
		while self.bfs(n, m, source, sink, parent, graph):
			path_flow = inf
			s = sink
			while s != source:
				p = parent[s]
				path_flow = min(path_flow, graph.adjMat[p][s])
				s = p
			max_flow += path_flow
			s = sink
			while s != source:
				p = parent[s]
				adjMat[p][s] -= path_flow
				adjMat[s][p] += path_flow
				s = p
		return max_flow


from collections import deque

class Dinic:

	def __init__(self, N):
		self._N = N
		self._caps = [dict() for _ in range(N)]
		self.INF = 10 ** 18

	def add_edge(self, u, v, cap):
		if cap == 0 or u == v:
			return
		if v not in self._caps[u]:
			self._caps[u][v] = 0
		self._caps[u][v] += cap

	def _flow(self, f, t, v):
		self._caps[f][t] -= v
		self._caps[t][f] = self._caps[t].setdefault(f, 0) + v
		if self._caps[f][t] == 0:
			del self._caps[f][t]

	def _make_dist(self, source, sink):
		rev_paths = [[] for _ in range(self._N)]
		self._dist = [self.INF] * self._N
		self._dist[source] = 0
		queue = deque([source])
		found = self.INF
		while queue:
			now = queue.pop()
			if now == sink:
				found = self._dist[now]
			for nxt in self._caps[now]:
				if self._dist[nxt] != self.INF or self._dist[now] == found:
					if self._dist[nxt] == self._dist[now] + 1:
						rev_paths[nxt].append(now)
					continue
				self._dist[nxt] = self._dist[now] + 1
				rev_paths[nxt].append(now)
				queue.appendleft(nxt)
		if self._dist[sink] == self.INF:
			return False
		self._in_use = [False] * self._N
		self._in_use[sink] = True
		queue = deque([sink])
		while queue:
			now = queue.pop()
			for nxt in rev_paths[now]:
				if self._dist[nxt] == self._dist[now] - 1:
					if self._in_use[nxt] == True:
						continue
					self._in_use[nxt] = True
					queue.appendleft(nxt)
		return found + 1

	def _route_flow(self, source, sink):
		_len = self._make_dist(source, sink)
		if _len == False:
			return 0
		f_nodes = [0] * _len
		f_limit = [self.INF] * _len
		f_suspend = [0] * _len
		prev_dist = -1
		queue = [source]
		while queue:
			now = queue.pop()
			d = self._dist[now]
			f_nodes[d] = now
			if prev_dist < d:
				if now != source:
					prev_limit = f_limit[d - 1]
					if prev_limit == 0:
						while queue and self._dist[queue[-1]] >= d - 1:
							queue.pop()
						continue
					if prev_limit > self._caps[f_nodes[d - 1]][now]:
						f_limit[d] = self._caps[f_nodes[d - 1]][now]
					else:
						f_limit[d] = prev_limit
				if now == sink:
					f_suspend[d] = f_limit[d]
				for nxt in self._caps[now]:
					if self._dist[nxt] == d + 1 and self._in_use[nxt]:
						queue.append(now)
						queue.append(nxt)
			else:
				vol = f_suspend[d + 1]
				if vol != 0:
					f_suspend[d + 1] = 0
					f_suspend[d] += vol
					self._flow(f_nodes[d], f_nodes[d + 1], vol)
					f_limit[d] -= vol
			prev_dist = d
		return f_suspend[0]

	def get_max_flow(self, source, sink):
		result = 0
		while True:
			flowed = self._route_flow(source, sink)
			if flowed != 0:
				result += flowed
			else:
				break
		return [result, self._caps]

class Solution:

	def findMaxFlow(self, N, M, Edges):
		nf = Dinic(N)
		for (u, v, c) in Edges:
			nf.add_edge(u - 1, v - 1, c)
			nf.add_edge(v - 1, u - 1, c)
		return nf.get_max_flow(0, N - 1)[0]


import collections

class Solution:

	def bfs(self, V, adj, visited, parent, target, ind):
		queue = collections.deque([])
		queue.append((ind, 999999999, -1))
		target_found = False
		max_flow = 0
		while queue:
			(index, maximum, pr) = queue.popleft()
			parent[index] = pr
			if index == target:
				target_found = True
				max_flow = maximum
				break
			if not visited[index]:
				visited[index] = True
				for i in adj[index].keys():
					w = adj[index][i]
					if not visited[i] and w > 0:
						queue.append((i, min(maximum, w), index))
		if target_found:
			v = target
			while parent[v] != -1:
				adj[parent[v]][v] -= max_flow
				adj[v][parent[v]] += max_flow
				v = parent[v]
		return (target_found, max_flow)

	def findMaxFlow(self, N, M, Edges):
		adj = [dict() for i in range(N + 1)]
		for edge in Edges:
			val = edge[2]
			if adj[edge[0]].get(edge[1]):
				val += adj[edge[0]][edge[1]]
			adj[edge[0]][edge[1]] = val
			adj[edge[1]][edge[0]] = val
		target_found = True
		total_flow = 0
		while target_found:
			visited = [False] * (N + 1)
			parent = [-1] * (N + 1)
			(target_found, max_flow) = self.bfs(N, adj, visited, parent, N, 1)
			total_flow += max_flow
		return total_flow


from queue import deque

class Solution:

	def bfs(self, source, sink, N):
		min_cap = 1000000000.0
		for i in range(len(self.parent)):
			self.parent[i] = -1
		vis = [False for i in range(N)]
		q = deque([source])
		vis[source] = True
		self.parent[source] = -1
		while q:
			u = q.popleft()
			for v in range(N):
				if vis[v] == False and self.graph[u][v] != 0:
					if v == sink:
						self.parent[v] = u
						min_cap = min(min_cap, self.graph[u][v])
						return min_cap
					q.append(v)
					vis[v] = True
					min_cap = min(min_cap, self.graph[u][v])
					self.parent[v] = u
		return 0

	def ford_fulkerson(self, source, sink, N):
		self.parent = [-1 for i in range(N)]
		res = 0
		while True:
			min_cap = self.bfs(source, sink, N)
			if min_cap == 0:
				break
			res += min_cap
			v = sink
			while v != source:
				u = self.parent[v]
				self.graph[u][v] -= min_cap
				self.graph[v][u] += min_cap
				v = self.parent[v]
		return res

	def findMaxFlow(self, N, M, Edges):
		self.graph = [[0 for i in range(N)] for j in range(N)]
		for e in Edges:
			self.graph[e[0] - 1][e[1] - 1] += e[2]
			self.graph[e[1] - 1][e[0] - 1] += e[2]
		return self.ford_fulkerson(0, N - 1, N)


class Solution:

	def findMaxFlow(self, N, M, Edges):
		g = [[0] * N for i in range(N)]
		for (i, j, k) in Edges:
			g[i - 1][j - 1] += k
			g[j - 1][i - 1] += k

		def bfs(s, t, parent):
			queue = [(s, float('inf'))]
			while queue:
				(curr, flow) = queue.pop(0)
				for (k, v) in enumerate(g[curr]):
					if parent[k] is None and v > 0:
						parent[k] = curr
						val = min(flow, v)
						if k == t:
							return val
						queue.append((k, val))
			return 0

		def helper(s, t):
			path = 0
			while True:
				parent = [None] * N
				parent[s] = -1
				val = bfs(s, t, parent)
				if val == 0:
					break
				path += val
				curr = t
				while curr != s:
					prev = parent[curr]
					g[prev][curr] -= val
					g[curr][prev] -= val
					curr = prev
			return path
		return helper(0, N - 1)


class Edge:

	def __init__(self, vertex, flow, capacity, reversed_edge=None):
		self.vertex = vertex
		self.flow = flow
		self.capacity = capacity
		self.reversed_edge = reversed_edge

class Graph:

	def __init__(self, n):
		self.n = n
		self.adj = [list() for _ in range(n)]
		self.level = [0] * n

	def add_edge(self, u, v, capacity):
		a = Edge(v, 0, capacity)
		b = Edge(u, 0, capacity, a)
		a.reversed_edge = b
		self.adj[u].append(a)
		self.adj[v].append(b)

	def bfs(self, s, t):
		self.level = [-1] * self.n
		self.level[s] = 0
		queue = [s]
		while queue:
			u = queue.pop(0)
			for edge in self.adj[u]:
				if edge.capacity > edge.flow and self.level[edge.vertex] < 0:
					self.level[edge.vertex] = self.level[u] + 1
					queue.append(edge.vertex)
		return self.level[t] > 0

	def dfs(self, u, t, flow):
		if u == t:
			return flow
		for edge in self.adj[u]:
			if edge.capacity > edge.flow and self.level[edge.vertex] == self.level[u] + 1:
				d_flow_to_u = min(flow, edge.capacity - edge.flow)
				d_flow_path = self.dfs(edge.vertex, t, d_flow_to_u)
				if d_flow_path > 0:
					edge.flow += d_flow_path
					edge.reversed_edge.flow -= d_flow_path
					return d_flow_path
		return 0

	def max_flow(self, s, t):
		max_flow = 0
		while self.bfs(s, t):
			max_flow += self.dfs(s, t, float('inf'))
		return max_flow

class Solution:

	def findMaxFlow(self, N, M, Edges):
		graph = Graph(N)
		for (u, v, capacity) in Edges:
			graph.add_edge(u - 1, v - 1, capacity)
		return graph.max_flow(0, N - 1)


from collections import defaultdict

class Solution:

	def solve(self, N, M, Edges):
		self.v = N
		self.g = defaultdict(list)
		self.res = [[0] * (N + 1) for i in range(N + 1)]
		for (a, b, f) in Edges:
			self.g[a].append(b)
			self.g[b].append(a)
			self.res[a][b] += f
			self.res[b][a] += f
		return self.karp(1, N)

	def karp(self, source, sink):
		max_flow = 0
		augPathMinFlow = self.bfs(source, sink)
		while augPathMinFlow is not None:
			max_flow = max_flow + augPathMinFlow
			current = sink
			while current != source:
				prev = self.parent[current]
				self.res[prev][current] -= augPathMinFlow
				self.res[current][prev] += augPathMinFlow
				current = prev
			augPathMinFlow = self.bfs(source, sink)
		return max_flow

	def bfs(self, source, sink):
		self.parent = [-1 for i in range(self.v + 1)]
		self.parent[source] = -2
		q = [(source, float('inf'))]
		while len(q) > 0:
			(current, flow) = q.pop(0)
			for adjacent in self.g[current]:
				if self.parent[adjacent] == -1 and self.res[current][adjacent] != 0:
					self.parent[adjacent] = current
					new_flow = min(flow, self.res[current][adjacent])
					if adjacent == sink:
						return new_flow
					q.append((adjacent, new_flow))
		return None


class Solution:

	def solve(self, N, M, Edges):
		graph = [[0] * N for _ in range(N)]
		for (frm, to, flow) in Edges:
			graph[frm - 1][to - 1] += flow
			graph[to - 1][frm - 1] += flow

		def bfs(graph, s, t, parent):
			q = [(s, float('inf'))]
			while q:
				(cur, flow) = q.pop(0)
				for (ind, val) in enumerate(graph[cur]):
					if parent[ind] == -1 and val > 0:
						flow = min(flow, val)
						q.append((ind, flow))
						parent[ind] = cur
						if ind == t:
							return flow
			return 0

		def maxflow(graph, source, sink):
			max_flow = 0
			while True:
				parent = [-1] * N
				parent[source] = -2
				flow = bfs(graph, source, sink, parent)
				if flow == 0:
					break
				max_flow += flow
				v = sink
				while v != source:
					u = parent[v]
					graph[u][v] -= flow
					graph[v][u] += flow
					v = parent[v]
			return max_flow
		return maxflow(graph, 0, N - 1)


class Solution:

	def solve(self, N, M, Edges):
		self.graph = [[0] * N for _ in range(N)]
		for (frm, to, flow) in Edges:
			self.graph[frm - 1][to - 1] += flow
			self.graph[to - 1][frm - 1] += flow
		return self.maxflow(0, N - 1, N)

	def bfs(self, s, t, parent):
		visited = [False] * len(parent)
		queue = []
		queue.append((s, float('inf')))
		visited[s] = True
		while queue:
			(u, flow) = queue.pop(0)
			for (ind, val) in enumerate(self.graph[u]):
				if visited[ind] == False and val > 0:
					flow = min(flow, val)
					queue.append((ind, flow))
					visited[ind] = True
					parent[ind] = u
					if ind == t:
						return flow
		return 0

	def maxflow(self, source, sink, n):
		parent = [-1] * n
		max_flow = 0
		while True:
			flow = self.bfs(source, sink, parent)
			if flow == 0:
				break
			max_flow += flow
			v = sink
			while v != source:
				u = parent[v]
				self.graph[u][v] -= flow
				self.graph[v][u] += flow
				v = parent[v]
		return max_flow


class Solution:

	def solve(self, N, M, Edges):
		self.graph = [[0] * N for _ in range(N)]
		self.ROW = len(self.graph)
		for (frm, to, flow) in Edges:
			self.graph[frm - 1][to - 1] += flow
			self.graph[to - 1][frm - 1] += flow
		return self.FordFulkerson(0, self.ROW - 1)

	def BFS(self, s, t, parent):
		visited = [False] * self.ROW
		queue = []
		queue.append(s)
		visited[s] = True
		while queue:
			u = queue.pop(0)
			for (ind, val) in enumerate(self.graph[u]):
				if visited[ind] == False and val > 0:
					queue.append(ind)
					visited[ind] = True
					parent[ind] = u
					if ind == t:
						return True
		return False

	def FordFulkerson(self, source, sink):
		parent = [-1] * self.ROW
		max_flow = 0
		while self.BFS(source, sink, parent):
			path_flow = float('Inf')
			s = sink
			while s != source:
				path_flow = min(path_flow, self.graph[parent[s]][s])
				s = parent[s]
			max_flow += path_flow
			v = sink
			while v != source:
				u = parent[v]
				self.graph[u][v] -= path_flow
				self.graph[v][u] += path_flow
				v = parent[v]
		return max_flow