Given a square grid of size N, each cell of which contains integer cost which represents a cost to traverse through that cell, we need to find a path from top left cell to bottom right cell by which the total cost incurred is minimum.
From the cell (i,j) we can go (i,j-1), (i, j+1), (i-1, j), (i+1, j). 
Note: It is assumed that negative cost cycles do not exist in the input matrix.
 
Example 1:
Input: grid = {{9,4,9,9},{6,7,6,4},
{8,3,3,7},{7,4,9,10}}
Output: 43
Explanation: The grid is-
9 4 9 9
6 7 6 4
8 3 3 7
7 4 9 10
The minimum cost is-
9 + 4 + 7 + 3 + 3 + 7 + 10 = 43.
Example 2:
Input: grid = {{4,4},{3,7}}
Output: 14
Explanation: The grid is-
4 4
3 7
The minimum cost is- 4 + 3 + 7 = 14.
 
Your Task:
You don't need to read or print anything. Your task is to complete the function minimumCostPath() which takes grid as input parameter and returns the minimum cost to react at bottom right cell from top left cell.
 
Expected Time Compelxity: O(n^{2}*log(n))
Expected Auxiliary Space: O(n^{2}) 
 
Constraints:
1 ≤ n ≤ 500
1 ≤ cost of cells ≤ 1000

Source: geeksforgeeks | Difficulty: MEDIUM_HARD
Tags: Graph algorithms

Data structures

Greedy algorithms

Starter code: class Solution:
    
    #Function to return the minimum cost to react at bottom
	#right cell from top left cell.
	def minimumCostPath(self, grid):
		#Code here

Solutions:
from heapq import *

class Solution:

	def minimumCostPath(self, grid):
		m = len(grid)
		n = len(grid[0])
		min_heap = []
		heappush(min_heap, (grid[0][0], (0, 0)))
		dist = [[float('inf') for j in range(n)] for i in range(m)]
		dist[0][0] = grid[0][0]
		while min_heap:
			(d, (i, j)) = heappop(min_heap)
			if i > 0:
				relax((i, j), (i - 1, j), grid[i - 1][j], dist, min_heap)
			if i < m - 1:
				relax((i, j), (i + 1, j), grid[i + 1][j], dist, min_heap)
			if j > 0:
				relax((i, j), (i, j - 1), grid[i][j - 1], dist, min_heap)
			if j < n - 1:
				relax((i, j), (i, j + 1), grid[i][j + 1], dist, min_heap)
		return dist[-1][-1]

def relax(u, v, e, dist, min_heap):
	(i, j) = u
	(x, y) = v
	if dist[x][y] > dist[i][j] + e:
		dist[x][y] = dist[i][j] + e
		heappush(min_heap, (dist[x][y], v))


import heapq
from collections import defaultdict

class Solution:

	def minimumCostPath(self, grid):
		n = len(grid)
		minHeap = [(grid[0][0], (0, 0))]
		done = set()
		cost = {}
		while minHeap:
			(c1, (i, j)) = heapq.heappop(minHeap)
			if (i, j) in done:
				continue
			done.add((i, j))
			cost[i, j] = c1
			for (di, dj) in [(0, 1), (1, 0), (0, -1), (-1, 0)]:
				(ni, nj) = (i + di, j + dj)
				if 0 <= ni < n and 0 <= nj < n:
					if (ni, nj) in done:
						continue
					heapq.heappush(minHeap, (c1 + grid[ni][nj], (ni, nj)))
		return cost[n - 1, n - 1]


import heapq

class Solution:

	def minimumCostPath(self, grid):
		heap = [(grid[0][0], 0, 0)]
		heapq.heapify(heap)
		s = set()
		s.add((0, 0))
		n = len(grid)
		while heap:
			(dis, i, j) = heapq.heappop(heap)
			if i == n - 1 and j == n - 1:
				return dis
			di = [(-1, 0), (1, 0), (0, -1), (0, 1)]
			for k in di:
				r = i + k[0]
				c = j + k[1]
				if r >= 0 and r < n and (c >= 0) and (c < n) and ((r, c) not in s):
					heapq.heappush(heap, (dis + grid[r][c], r, c))
					s.add((r, c))
		return dis


from collections import defaultdict
import heapq

class Solution:

	def minimumCostPath(self, grid):
		n = len(grid)
		m = len(grid[0])
		limit = n + m - 3
		visited = set()
		heap = [(grid[0][0], 0, 0)]
		while True:
			(time, i, j) = heapq.heappop(heap)
			if i + j == limit:
				return time + grid[n - 1][m - 1]
			if i > 0 and (not (i - 1, j) in visited):
				visited.add((i - 1, j))
				heapq.heappush(heap, (time + grid[i - 1][j], i - 1, j))
			if i < n - 1 and (not (i + 1, j) in visited):
				visited.add((i + 1, j))
				heapq.heappush(heap, (time + grid[i + 1][j], i + 1, j))
			if j > 0 and (not (i, j - 1) in visited):
				visited.add((i, j - 1))
				heapq.heappush(heap, (time + grid[i][j - 1], i, j - 1))
			if j < m - 1 and (not (i, j + 1) in visited):
				visited.add((i, j + 1))
				heapq.heappush(heap, (time + grid[i][j + 1], i, j + 1))


import heapq

class Solution:

	def minimumCostPath(self, grid):
		n = len(grid)
		m = len(grid[0])
		visited = set()
		heap = [(grid[0][0], 0, 0)]
		while True:
			(time, i, j) = heapq.heappop(heap)
			if (i, j) in visited:
				continue
			visited.add((i, j))
			if i == n - 1 and j == m - 1:
				return time
			if i > 0 and (not (i - 1, j) in visited):
				heapq.heappush(heap, (time + grid[i - 1][j], i - 1, j))
			if i < n - 1 and (not (i + 1, j) in visited):
				heapq.heappush(heap, (time + grid[i + 1][j], i + 1, j))
			if j > 0 and (not (i, j - 1) in visited):
				heapq.heappush(heap, (time + grid[i][j - 1], i, j - 1))
			if j < m - 1 and (not (i, j + 1) in visited):
				heapq.heappush(heap, (time + grid[i][j + 1], i, j + 1))


import math
import heapq as hq

class Solution:

	def isValid(self, x, y, n):
		return x >= 0 and x < n and (y >= 0) and (y < n)

	def minimumCostPath(self, grid):
		n = len(grid)
		dx = [-1, 1, 0, 0]
		dy = [0, 0, -1, 1]
		s = [0, 0]
		q = []
		dp = [[math.inf for i in range(n)] for j in range(n)]
		dp[0][0] = grid[0][0]
		hq.heappush(q, (dp[0][0], s))
		while len(q):
			(d_v, v) = hq.heappop(q)
			if dp[v[0]][v[1]] != d_v:
				continue
			for i in range(4):
				x = v[0] + dx[i]
				y = v[1] + dy[i]
				if self.isValid(x, y, n) and dp[x][y] > dp[v[0]][v[1]] + grid[x][y]:
					dp[x][y] = dp[v[0]][v[1]] + grid[x][y]
					hq.heappush(q, (dp[x][y], [x, y]))
		return dp[n - 1][n - 1]


import heapq

class Solution:

	def minimumCostPath(self, grid):
		hp = []
		heapq.heappush(hp, [grid[0][0], 0, 0])
		n = len(grid)
		s_set = set()
		s_set.add((0, 0))
		dir = [[0, 1], [0, -1], [1, 0], [-1, 0]]
		while hp:
			(dis, i, j) = heapq.heappop(hp)
			if i == n - 1 and j == n - 1:
				return dis
			for (x, y) in dir:
				new_x = x + i
				new_y = y + j
				if new_x < 0 or new_x >= n or new_y < 0 or (new_y >= n) or ((new_x, new_y) in s_set):
					continue
				heapq.heappush(hp, [dis + grid[new_x][new_y], new_x, new_y])
				s_set.add((new_x, new_y))


from heapq import *

class Solution:

	def minimumCostPath(self, grid):
		row = len(grid)
		col = len(grid[0])
		directions = [[0, 1], [1, 0], [0, -1], [-1, 0]]
		queue = []
		heappush(queue, (grid[0][0], 0, 0))
		grid[0][0] = -1
		while queue:
			(cnt, x, y) = heappop(queue)
			if x == row - 1 and y == col - 1:
				return cnt
			for (i, j) in directions:
				new_x = x + i
				new_y = y + j
				if new_x >= 0 and new_x < row and (new_y >= 0) and (new_y < col) and (grid[new_x][new_y] != -1):
					heappush(queue, (cnt + grid[new_x][new_y], new_x, new_y))
					grid[new_x][new_y] = -1
		return -1


from heapq import heapify, heappush, heappop

class Solution:

	def minimumCostPath(self, grid):
		n = len(grid)
		heap = [(grid[0][0], 0, 0)]
		heapify(heap)
		v = set((0, 0))
		while heap:
			(val, i, j) = heappop(heap)
			if i == n - 1 and j == n - 1:
				return val
			if i < n - 1 and (i + 1, j) not in v:
				heappush(heap, (val + grid[i + 1][j], i + 1, j))
				v.add((i + 1, j))
			if i > 0 and (i - 1, j) not in v:
				heappush(heap, (val + grid[i - 1][j], i - 1, j))
				v.add((i - 1, j))
			if j < n - 1 and (i, j + 1) not in v:
				heappush(heap, (val + grid[i][j + 1], i, j + 1))
				v.add((i, j + 1))
			if j > 0 and (i, j - 1) not in v:
				heappush(heap, (val + grid[i][j - 1], i, j - 1))
				v.add((i, j - 1))
		return val


class Solution:

	def minimumCostPath(self, grid):
		import heapq
		l = []
		heapq.heapify(l)
		n = len(grid)
		visited = [[False for j in range(n)] for i in range(n)]
		heapq.heappush(l, (grid[0][0], 0, 0))
		visited[0][0] = True
		while len(l):
			(d, i, j) = heapq.heappop(l)
			if i == n - 1 and j == n - 1:
				return d
			dx = [1, 0, 0, -1]
			dy = [0, -1, 1, 0]
			for r in range(4):
				x = i + dx[r]
				y = j + dy[r]
				if x >= 0 and x < n and (y >= 0) and (y < n) and (not visited[x][y]):
					visited[x][y] = True
					heapq.heappush(l, (d + grid[x][y], x, y))


from heapq import heappush, heappop

class Solution:

	def minimumCostPath(self, grid):
		n = len(grid)
		distance = [[10 ** 9] * n for _ in range(n)]
		distance[0][0] = grid[0][0]
		heap = []
		heappush(heap, (distance[0][0], (0, 0)))
		while heap:
			(curr_dist, cell) = heappop(heap)
			(u, v) = (cell[0], cell[1])
			for (uu, vv) in [[-1 + u, v], [1 + u, v], [u, -1 + v], [u, 1 + v]]:
				if 0 <= uu < n and 0 <= vv < n:
					if curr_dist + grid[uu][vv] < distance[uu][vv]:
						distance[uu][vv] = curr_dist + grid[uu][vv]
						heappush(heap, (distance[uu][vv], (uu, vv)))
		return distance[n - 1][n - 1]


class Solution:

	def minimumCostPath(self, grid):

		def Dijkstra(G, s):

			def relax(G, d, v, u, c):
				if d[v[0]][v[1]] > d[u[0]][u[1]] + c:
					d[v[0]][v[1]] = d[u[0]][u[1]] + c
					return True
				return False
			n = len(G)
			from math import inf
			from queue import PriorityQueue
			d = [[inf for _ in range(n)] for _ in range(n)]
			Q = PriorityQueue()
			d[s[0]][s[1]] = G[s[0]][s[1]]
			Q.put((d[s[0]][s[1]], s))
			while not Q.empty():
				(w, u) = Q.get()
				if w == d[u[0]][u[1]]:
					d[u[0]][u[1]] = w
					for (i, j) in [(0, -1), (0, 1), (-1, 0), (1, 0)]:
						if 0 <= u[0] + i < n and 0 <= u[1] + j < n:
							if relax(G, d, (u[0] + i, u[1] + j), u, G[u[0] + i][u[1] + j]):
								Q.put((d[u[0] + i][u[1] + j], (u[0] + i, u[1] + j)))
			return d
		return Dijkstra(grid, (0, 0))[len(grid) - 1][len(grid) - 1]


import heapq

class Solution:

	def minimumCostPath(self, grid):
		heap = [(grid[0][0], 0, 0)]
		heapq.heapify(heap)
		myset = set()
		myset.add((0, 0))
		n = len(grid)
		while heap:
			(distance, i, j) = heapq.heappop(heap)
			if i == n - 1 and j == n - 1:
				return distance
			dis_arr = [(-1, 0), (1, 0), (0, -1), (0, 1)]
			for x in dis_arr:
				r = i + x[0]
				c = j + x[1]
				if r >= 0 and r < n and (c >= 0) and (c < n) and ((r, c) not in myset):
					heapq.heappush(heap, (distance + grid[r][c], r, c))
					myset.add((r, c))
		return distance


import heapq

class Solution:

	def minimumCostPath(self, grid):
		heap = [[grid[0][0], 0, 0]]
		heapq.heapify(heap)
		visited = set()
		visited.add((0, 0))
		row = len(grid)
		col = len(grid)
		while heap:
			(dis, i, j) = heapq.heappop(heap)
			directions = [[1, 0], [-1, 0], [0, 1], [0, -1]]
			if i == row - 1 and j == col - 1:
				return dis
			for k in directions:
				r = k[0] + i
				c = k[1] + j
				if r >= 0 and r < row and (c >= 0) and (c < col) and ((r, c) not in visited):
					heapq.heappush(heap, [dis + grid[r][c], r, c])
					visited.add((r, c))
		return dis


import math

class Solution:

	def minimumCostPath(self, grid):
		n = len(grid)
		import sys
		sys.setrecursionlimit(10 ** 9)
		import heapq
		visited = [[False for i in range(n)] for j in range(n)]
		li = []
		heapq.heapify(li)
		dx = [-1, 0, 0, 1]
		dy = [0, -1, 1, 0]
		visited[0][0] = True
		heapq.heappush(li, (grid[0][0], 0, 0))
		while len(li):
			(dist, i, j) = heapq.heappop(li)
			if i == n - 1 and j == n - 1:
				return dist
			for r in range(4):
				x = i + dx[r]
				y = j + dy[r]
				if x >= 0 and x < n and (y >= 0) and (y < n) and (not visited[x][y]):
					visited[x][y] = True
					heapq.heappush(li, (dist + grid[x][y], x, y))


from queue import PriorityQueue

class Solution:

	def minimumCostPath(self, grid):
		dist = [[float('infinity') for _ in range(len(grid))] for _ in range(len(grid))]
		p = PriorityQueue()
		dist[0][0] = grid[0][0]
		p.put((grid[0][0], 0, 0))
		while not p.empty():
			dt = p.get()
			(wt, row, col) = (dt[0], dt[1], dt[2])
			if row == len(grid) - 1 and col == len(grid[0]) - 1:
				return wt
			dltRow = [0, 0, -1, 1]
			dltCol = [-1, 1, 0, 0]
			for i in range(len(dltRow)):
				(newRow, newCol) = (row + dltRow[i], col + dltCol[i])
				if newRow >= 0 and newRow < len(grid) and (newCol >= 0) and (newCol < len(grid[0])) and (wt + grid[newRow][newCol] < dist[newRow][newCol]):
					dist[newRow][newCol] = wt + grid[newRow][newCol]
					p.put((wt + grid[newRow][newCol], newRow, newCol))


from queue import PriorityQueue

class Solution:

	def minimumCostPath(self, grid):
		N = len(grid)
		M = len(grid[0])
		dp = [[float('inf') for _ in range(M)] for _ in range(N)]
		pq = PriorityQueue()
		dp[0][0] = grid[0][0]
		pq.put((grid[0][0], 0, 0))
		while len(pq.queue) > 0:
			(dist, i, j) = pq.get()
			if i == N - 1 and j == N - 1:
				break
			for (x, y) in [(i, j - 1), (i, j + 1), (i - 1, j), (i + 1, j)]:
				if x >= 0 and x < N and (y >= 0) and (y < M):
					if dp[x][y] >= dp[i][j] + grid[x][y]:
						dp[x][y] = dp[i][j] + grid[x][y]
						pq.put((dp[x][y], x, y))
		return dp[N - 1][M - 1]


class Solution:

	def minimumCostPath(self, grid):
		import heapq

class Solution:

	def minimumCostPath(self, grid):
		from collections import defaultdict
		d = defaultdict(list)
		di = [(-1, 0), (1, 0), (0, -1), (0, 1)]
		for i in range(len(grid)):
			for j in range(len(grid[0])):
				for (x, y) in di:
					if 0 <= x + i <= len(grid) - 1 and 0 <= y + j <= len(grid[0]) - 1:
						d[i, j].append((x + i, y + j))
		import heapq
		heap = [(grid[0][0], 0, 0)]
		heapq.heapify(heap)
		s = set()
		s.add((0, 0))
		n = len(grid)
		while heap:
			(dis, i, j) = heapq.heappop(heap)
			if i == n - 1 and j == n - 1:
				return dis
			for (r, c) in d[i, j]:
				if (r, c) not in s:
					heapq.heappush(heap, (dis + grid[r][c], r, c))
					s.add((r, c))
		return dis


import heapq

class Solution:

	def isSafe(self, x, y, R, C):
		return x >= 0 and x < R and (y >= 0) and (y < C)

	def minimumCostPath(self, grid):
		C = len(grid[0])
		R = len(grid)
		cost = grid
		dx = [1, 0, 0, -1]
		dy = [0, 1, -1, 0]
		dp = [[0 for x in range(C)] for x in range(R)]
		visited = [[False for x in range(C)] for x in range(R)]
		for i in range(R):
			for j in range(C):
				dp[i][j] = float('Inf')
				visited[i][j] = False
		pq = []
		dp[0][0] = cost[0][0]
		heapq.heappush(pq, (cost[0][0], [0, 0]))
		while len(pq):
			cell = heapq.heappop(pq)[1]
			x = cell[0]
			y = cell[1]
			if visited[x][y]:
				continue
			visited[x][y] = True
			for i in range(4):
				next_x = x + dx[i]
				next_y = y + dy[i]
				if self.isSafe(next_x, next_y, R, C) and (not visited[next_x][next_y]):
					dp[next_x][next_y] = min(dp[next_x][next_y], dp[x][y] + cost[next_x][next_y])
					heapq.heappush(pq, (dp[next_x][next_y], [next_x, next_y]))
		return dp[R - 1][C - 1]


import heapq

class Solution:

	def minimumCostPath(self, grid):
		direction = [[0, 1], [-1, 0], [1, 0], [0, -1]]
		heap = []
		heapq.heappush(heap, [grid[0][0], 0, 0])
		distance = [[9999999 for i in range(len(grid))] for j in range(len(grid[0]))]
		distance[0][0] = grid[0][0]
		while heap:
			(dis, i, j) = heapq.heappop(heap)
			tempi = i
			tempj = j
			for poin in direction:
				tempi = i + poin[0]
				tempj = j + poin[1]
				if 0 <= tempi < len(grid) and 0 <= tempj < len(grid[0]):
					if distance[tempi][tempj] > dis + grid[tempi][tempj]:
						distance[tempi][tempj] = dis + grid[tempi][tempj]
						heapq.heappush(heap, [distance[tempi][tempj], tempi, tempj])
		return distance[-1][-1]


class Solution:

	def minimumCostPath(self, grid):
		import queue
		from queue import PriorityQueue
		(m, n) = (len(grid), len(grid[0]))
		dist = [[1000000000.0 for i in range(n)] for j in range(n)]
		q = PriorityQueue()
		q.put((grid[0][0], 0, 0))
		dx = [0, 0, -1, 1]
		dy = [-1, 1, 0, 0]
		while not q.empty():
			top = q.get()
			val = top[0]
			a = top[1]
			b = top[2]
			if dist[a][b] < 100000000.0:
				continue
			dist[a][b] = val
			for i in range(4):
				x = a + dx[i]
				y = b + dy[i]
				if x < 0 or y < 0 or x >= m or (y >= n):
					continue
				if dist[x][y] <= 100000000.0:
					continue
				dist[x][y] = 100000000.0
				q.put((val + grid[x][y], x, y))
		return int(dist[m - 1][n - 1])


import heapq

class Solution:

	def minimumCostPath(self, grid):
		(n, m) = (len(grid), len(grid[0]))
		Cost = [[float('inf') for _ in range(m)] for _ in range(n)]
		Cost[0][0] = grid[0][0]
		pq = []
		heapq.heappush(pq, (Cost[0][0], (0, 0)))
		while pq:
			(dis, u) = heapq.heappop(pq)
			(x, y) = (u[0], u[1])
			dx = [-1, 0, 1, 0]
			dy = [0, 1, 0, -1]
			for i in range(4):
				new_x = x + dx[i]
				new_y = y + dy[i]
				if new_x >= 0 and new_x < n and (new_y >= 0) and (new_y < m):
					if dis + grid[new_x][new_y] < Cost[new_x][new_y]:
						Cost[new_x][new_y] = dis + grid[new_x][new_y]
						heapq.heappush(pq, (Cost[new_x][new_y], (new_x, new_y)))
		return Cost[n - 1][m - 1]


import heapq as h

class Solution:

	def minimumCostPath(self, grid):
		(n, m) = (len(grid), len(grid[0]))
		cost = [[float('inf') for i in range(m)] for j in range(n)]
		mat = [[-1, 0], [0, -1], [1, 0], [0, 1]]
		q = []
		cost[0][0] = grid[0][0]
		q.append([grid[0][0], 0, 0])
		ans = 0
		while q:
			node = h.heappop(q)
			(x, y) = (node[1], node[2])
			if node[0] > cost[x][y]:
				continue
			if x == n - 1 and y == m - 1:
				return node[0]
			for ele in mat:
				(x1, y1) = (x + ele[0], y + ele[1])
				if x1 >= 0 and x1 < n and (y1 >= 0) and (y1 < m):
					if cost[x1][y1] > node[0] + grid[x1][y1]:
						h.heappush(q, [node[0] + grid[x1][y1], x1, y1])
						cost[x1][y1] = node[0] + grid[x1][y1]


import heapq
adjacent = [(0, -1), (0, 1), (-1, 0), (1, 0)]

def validNeighbors(row, col, n):
	result = []
	for step in adjacent:
		(s_row, s_col) = step
		n_row = row + s_row
		n_col = col + s_col
		if n_row >= 0 and n_row <= n - 1 and (n_col >= 0) and (n_col <= n - 1):
			result.append((n_row, n_col))
	return result

class Solution:

	def minimumCostPath(self, grid):
		n = len(grid)
		distance = [[0 for i in range(n)] for j in range(n)]
		visited = [[False for i in range(n)] for j in range(n)]
		distance[0][0] = grid[0][0]
		heap = []
		heapq.heappush(heap, (distance[0][0], 0, 0))
		while len(heap) > 0:
			(dist, row, col) = heapq.heappop(heap)
			if not visited[row][col]:
				visited[row][col] = True
				neighbors = validNeighbors(row, col, n)
				for neighbor in neighbors:
					(n_row, n_col) = neighbor
					if distance[n_row][n_col] == 0 or distance[n_row][n_col] > distance[row][col] + grid[n_row][n_col]:
						distance[n_row][n_col] = distance[row][col] + grid[n_row][n_col]
						heapq.heappush(heap, (distance[n_row][n_col], n_row, n_col))
		return distance[n - 1][n - 1]


import heapq

class Solution:

	def minimumCostPath(self, grid):
		n = len(grid)
		m = len(grid[0])
		q = [(0, 0, 0)]
		c = [[True for j in range(m)] for i in range(n)]
		d = [[1000000000.0 for j in range(m)] for i in range(n)]
		d[0][0] = grid[0][0]
		heapq.heapify(q)
		for k in range(n * m):
			(dist, i, j) = heapq.heappop(q)
			while not c[i][j]:
				(dist, i, j) = heapq.heappop(q)
			if i - 1 >= 0 and c[i - 1][j] and (d[i][j] + grid[i - 1][j] < d[i - 1][j]):
				d[i - 1][j] = d[i][j] + grid[i - 1][j]
				heapq.heappush(q, (d[i - 1][j], i - 1, j))
			if i + 1 < n and c[i + 1][j] and (d[i][j] + grid[i + 1][j] < d[i + 1][j]):
				d[i + 1][j] = d[i][j] + grid[i + 1][j]
				heapq.heappush(q, (d[i + 1][j], i + 1, j))
			if j - 1 >= 0 and c[i][j - 1] and (d[i][j] + grid[i][j - 1] < d[i][j - 1]):
				d[i][j - 1] = d[i][j] + grid[i][j - 1]
				heapq.heappush(q, (d[i][j - 1], i, j - 1))
			if j + 1 < m and c[i][j + 1] and (d[i][j] + grid[i][j + 1] < d[i][j + 1]):
				d[i][j + 1] = d[i][j] + grid[i][j + 1]
				heapq.heappush(q, (d[i][j + 1], i, j + 1))
			c[i][j] = False
		return d[n - 1][m - 1]


import heapq

class Solution:

	def getNeighbors(self, i, j):
		candidates = [(i - 1, j), (i + 1, j), (i, j - 1), (i, j + 1)]
		valid_candidates = []
		for candidate in candidates:
			(row, col) = candidate
			if row < 0 or row >= self.num_rows or col < 0 or (col >= self.num_cols):
				continue
			if self.visited[row][col]:
				continue
			valid_candidates.append(candidate)
		return valid_candidates

	def minimumCostPath(self, grid):
		self.grid = grid
		(self.num_rows, self.num_cols) = (len(grid), len(grid[0]))
		self.visited = [[False for j in range(self.num_cols)] for i in range(self.num_rows)]
		q = [(self.grid[self.num_rows - 1][self.num_cols - 1], self.num_rows - 1, self.num_cols - 1)]
		self.visited[-1][-1] = True
		heapq.heapify(q)
		while q:
			(dist, i, j) = heapq.heappop(q)
			if i == 0 and j == 0:
				return dist
			neighbours = self.getNeighbors(i, j)
			for (n_i, n_j) in neighbours:
				self.visited[n_i][n_j] = True
				heapq.heappush(q, (dist + self.grid[n_i][n_j], n_i, n_j))
		return -1


import heapq
from heapq import heapify, heappush, heappop

class Solution:

	def minimumCostPath(self, grid):
		n = len(grid)
		visited = [[0 for i in range(n)] for j in range(n)]
		heap = [[grid[0][0], 0, 0]]
		delr = [-1, 0, 1, 0]
		delc = [0, 1, 0, -1]
		while len(heap) != 0:
			(cost, row, col) = heapq.heappop(heap)
			if row == n - 1 and col == n - 1:
				return cost
			else:
				for i in range(4):
					nrow = row + delr[i]
					ncol = col + delc[i]
					if 0 <= nrow < n and 0 <= ncol < n and (visited[nrow][ncol] == 0):
						visited[nrow][ncol] = 1
						heapq.heappush(heap, [cost + grid[nrow][ncol], nrow, ncol])
		return [-1]


class Solution:

	def minimumCostPath(self, grid):
		dp = [[float('inf') for i in range(len(grid[0]))] for i in range(len(grid))]
		dp[0][0] = grid[0][0]
		heap = [(0, (0, 0))]
		import heapq
		while heap:
			(dist, pos) = heapq.heappop(heap)
			(x, y) = pos
			for (i, j) in ((x + 1, y), (x, y + 1), (x - 1, y), (x, y - 1)):
				if 0 <= i < len(grid) and 0 <= j < len(grid[0]):
					if dp[i][j] > dp[x][y] + grid[i][j]:
						dp[i][j] = dp[x][y] + grid[i][j]
						heapq.heappush(heap, (dp[i][j], (i, j)))
		return dp[-1][-1]


import heapq

class Solution:

	def minimumCostPath(self, grid):
		n = len(grid)
		m = len(grid[0])
		dist = [[float('inf')] * m for _ in range(n)]
		pq = [(grid[0][0], (0, 0))]
		dist[0][0] = 0
		dr = [-1, 0, 1, 0]
		dc = [0, 1, 0, -1]
		while pq:
			(wt, (r, c)) = heapq.heappop(pq)
			for i in range(4):
				nrow = r + dr[i]
				ncol = c + dc[i]
				if 0 <= nrow < n and 0 <= ncol < m and (grid[nrow][ncol] + wt < dist[nrow][ncol]):
					dist[nrow][ncol] = grid[nrow][ncol] + wt
					if nrow == n - 1 and ncol == m - 1:
						return grid[nrow][ncol] + wt
					heapq.heappush(pq, (grid[nrow][ncol] + wt, (nrow, ncol)))


import heapq

class Solution:

	def minimumCostPath(self, grid):
		n = len(grid)
		heap = [(grid[0][0], 0, 0)]
		v = set((0, 0))
		while heap:
			(val, i, j) = heapq.heappop(heap)
			if i == n - 1 and j == n - 1:
				return val
			directions = [(0, 1), (1, 0), (-1, 0), (0, -1)]
			for (r, c) in directions:
				row = i + r
				col = j + c
				if row >= 0 and row < n and (col >= 0) and (col < n):
					if (row, col) not in v:
						heapq.heappush(heap, (val + grid[row][col], row, col))
						v.add((row, col))
		return val


import heapq

class Solution:

	def f(self, i, j, n, m):
		if i < 0 or j < 0 or i > n or (j > n):
			return False
		return True

	def minimumCostPath(self, grid):
		queue = [[grid[0][0], 0, 0]]
		dist = [[float('inf') for j in range(len(grid[0]))] for i in range(len(grid))]
		dist[0][0] = grid[0][0]
		dx = [1, 0, -1, 0]
		dy = [0, 1, 0, -1]
		while len(queue) != 0:
			t = heapq.heappop(queue)
			d = t[0]
			(x, y) = (t[1], t[2])
			for i in range(4):
				if self.f(x + dx[i], y + dy[i], len(grid) - 1, len(grid[0]) - 1):
					if dist[x + dx[i]][y + dy[i]] > d + grid[x + dx[i]][y + dy[i]]:
						dist[x + dx[i]][y + dy[i]] = d + grid[x + dx[i]][y + dy[i]]
						heapq.heappush(queue, [dist[x + dx[i]][y + dy[i]], x + dx[i], y + dy[i]])
		return dist[-1][-1]


import heapq

class Solution:

	def minimumCostPath(self, grid):
		N = len(grid)
		M = len(grid[0])
		visited = [[0 for i in range(M)] for j in range(N)]
		visited[0][0] = 1
		q = []
		q.append([grid[0][0], [0, 0]])
		r = [1, -1, 0, 0]
		c = [0, 0, -1, 1]
		while q:
			front = heapq.heappop(q)
			dist = front[0]
			row = front[1][0]
			col = front[1][1]
			if row == N - 1 and col == M - 1:
				return dist
			for i in range(4):
				x = row + r[i]
				y = col + c[i]
				if self.isvalid(x, y, grid, N, M) and visited[x][y] == 0:
					visited[x][y] = 1
					heapq.heappush(q, [dist + grid[x][y], [x, y]])

	def isvalid(self, newx, newy, A, N, M):
		if newx >= 0 and newx < N and (newy >= 0) and (newy < M):
			return True
		return False


import heapq

class Solution:

	def minimumCostPath(self, grid) -> int:
		row = len(grid)
		col = len(grid)
		heap = []
		dist = [[100000000.0] * len(grid) for i in range(len(grid))]
		dist[0][0] = 0
		heapq.heappush(heap, [grid[0][0], [0, 0]])
		direction = [[1, 0], [0, 1], [-1, 0], [0, -1]]
		while heap:
			element = heapq.heappop(heap)
			weight = element[0]
			for i in direction:
				x = element[1][0] + i[0]
				y = element[1][1] + i[1]
				if (x >= 0 and x < row) and (y >= 0 and y < col) and (grid[x][y] + weight < dist[x][y]):
					dist[x][y] = grid[x][y] + weight
					if x == row - 1 and y == row - 1:
						return dist[x][y]
					heapq.heappush(heap, [grid[x][y] + weight, [x, y]])


from heapq import heappush, heappop

class Solution:

	def minimumCostPath(self, grid):
		q = [(grid[0][0], 0, 0)]
		ans = 0
		di = [1, 0, -1, 0]
		dj = [0, 1, 0, -1]
		visited = set()
		visited.add((0, 0))
		while q:
			(totWeight, i, j) = heappop(q)
			if i == len(grid) - 1 and j == len(grid) - 1:
				return totWeight
			for d in range(4):
				newi = i + di[d]
				newj = j + dj[d]
				if 0 <= newi < len(grid) and 0 <= newj < len(grid):
					if (newi, newj) not in visited:
						heappush(q, (totWeight + grid[newi][newj], newi, newj))
						visited.add((newi, newj))


from heapq import heappop, heappush

class Solution:

	def isValid(self, row, col, n):
		if row < n and col < n and (row >= 0) and (col >= 0):
			return True
		return False

	def minimumCostPath(self, grid):
		n = len(grid)
		dr = [0, -1, 0, 1]
		dc = [1, 0, -1, 0]
		pq = [[grid[0][0], [0, 0]]]
		visited = [[0 for i in range(n)] for j in range(n)]
		visited[0][0] = 1
		while pq:
			top = heappop(pq)
			cost = top[0]
			row = top[1][0]
			col = top[1][1]
			if row == n - 1 and col == n - 1:
				return cost
			for i in range(4):
				adjrow = row + dr[i]
				adjcol = col + dc[i]
				if self.isValid(adjrow, adjcol, n) and visited[adjrow][adjcol] == 0:
					energy = grid[adjrow][adjcol]
					heappush(pq, [energy + cost, [adjrow, adjcol]])
					visited[adjrow][adjcol] = 1


import heapq as hq

class Solution:

	def minimumCostPath(self, grid):
		visited = [[False for _ in range(len(grid[0]))] for j in range(len(grid))]
		dist = [[float('inf') for _ in range(len(grid[0]))] for j in range(len(grid))]
		minH = []
		minH.append([grid[0][0], 0, 0])
		while minH:
			(cost, r, c) = hq.heappop(minH)
			if not visited[r][c]:
				visited[r][c] = True
				dist[r][c] = min(dist[r][c], cost)
				for (dx, dy) in [[0, 1], [1, 0], [-1, 0], [0, -1]]:
					nr = r + dx
					nc = c + dy
					if 0 <= nr < len(grid) and 0 <= nc < len(grid[0]) and (not visited[nr][nc]):
						hq.heappush(minH, [cost + grid[nr][nc], nr, nc])
		return dist[len(grid) - 1][len(grid[0]) - 1]


import heapq

class Solution:

	def minimumCostPath(self, grid):
		pq = [(grid[0][0], 0, 0)]
		dirc = [(-1, 0), (0, 1), (1, 0), (0, -1)]
		n = len(grid)
		dist = [[float('inf')] * n for _ in range(n)]
		dist[0][0] = grid[0][0]
		while pq:
			(dis, i, j) = heapq.heappop(pq)
			for (delRow, delCol) in dirc:
				nr = delRow + i
				nc = delCol + j
				if nr >= 0 and nc >= 0 and (nr < n) and (nc < n) and (dist[nr][nc] > dis + grid[nr][nc]):
					dist[nr][nc] = dis + grid[nr][nc]
					heapq.heappush(pq, (dist[nr][nc], nr, nc))
		return dist[n - 1][n - 1]


from heapq import heappush, heappop

class Solution:

	def minimumCostPath(self, grid):
		N = len(grid)
		heap = [(0, 0, 0)]
		INF = float('inf')
		cost = [[INF] * N for _ in range(N)]
		cost[0][0] = grid[0][0]
		while heap:
			(_, r, c) = heappop(heap)
			for (dr, dc) in [(0, 1), (1, 0), (0, -1), (-1, 0)]:
				(nr, nc) = (r + dr, c + dc)
				if 0 <= nr < N and 0 <= nc < N and (cost[nr][nc] > cost[r][c] + grid[nr][nc]):
					cost[nr][nc] = cost[r][c] + grid[nr][nc]
					heappush(heap, (cost[nr][nc], nr, nc))
		return cost[N - 1][N - 1]


class Solution:

	def heapify(self, queue, N, i):
		if i > -1:
			smallest = i
			l = 2 * i + 1
			r = 2 * i + 2
			if l < N and queue[l][0] < queue[smallest][0]:
				smallest = l
			if r < N and queue[r][0] < queue[smallest][0]:
				smallest = r
			if smallest != i:
				(queue[smallest], queue[i]) = (queue[i], queue[smallest])
				self.heapify(queue, N, smallest)

	def heapify_min(self, queue, N, i):
		if i > -1:
			smallest = i
			l = 2 * i + 1
			r = 2 * i + 2
			if l < N and queue[l][0] < queue[smallest][0]:
				smallest = l
			if r < N and queue[r][0] < queue[smallest][0]:
				smallest = r
			if smallest != i:
				(queue[smallest], queue[i]) = (queue[i], queue[smallest])
				self.heapify_min(queue, N, (i - 1) // 2)

	def valid_movement(self, d, x, y):
		return d[0] > -1 and d[1] > -1 and (d[0] < x) and (d[1] < y)

	def minimumCostPath(self, grid):
		queue = [0 for i in range(len(grid[0]) * len(grid))]
		queue[0] = (grid[0][0], 0, 0)
		arr_size = 1
		(x, y) = (len(grid), len(grid[0]))
		d = {(0, 0): True}
		while True:
			a = queue[0]
			queue[0] = queue[arr_size - 1]
			arr_size -= 1
			if arr_size:
				self.heapify(queue, arr_size, 0)
			(i, j) = (a[1], a[2])
			actions = [(i + 1, j), (i - 1, j), (i, j + 1), (i, j - 1)]
			for act in actions:
				if not self.valid_movement(act, x, y):
					continue
				if (act[0], act[1]) in d:
					continue
				d[act[0], act[1]] = True
				if act == (x - 1, y - 1):
					return a[0] + grid[-1][-1]
				queue[arr_size] = (a[0] + grid[act[0]][act[1]], act[0], act[1])
				arr_size += 1
				self.heapify_min(queue, arr_size, (arr_size - 2) // 2)


MAX = 1 << 32
from heapq import heappush, heappop, heapify

def dyj(A):
	N = len(A)
	M = len(A[0])
	pq = [[0, 0, 0]]
	heapify(pq)
	d = [[MAX for i in range(M)] for i in range(N)]
	dx = [0, 0, -1, 1]
	dy = [1, -1, 0, 0]
	d[0][0] = A[0][0]
	while pq:
		(w, x, y) = heappop(pq)
		for i in range(4):
			nx = dx[i] + x
			ny = dy[i] + y
			if nx >= 0 and nx < N and (ny >= 0) and (ny < M) and (d[nx][ny] > d[x][y] + A[nx][ny]):
				d[nx][ny] = d[x][y] + A[nx][ny]
				heappush(pq, [d[nx][ny], nx, ny])
	return d[-1][-1]

class Solution:

	def minimumCostPath(self, grid):
		return dyj(grid)


import heapq

class Solution:

	def minimumCostPath(self, grid):
		n = len(grid)
		q = []
		vis = [[100000000 for _ in range(n)] for _ in range(n)]
		vis[0][0] = grid[0][0]
		q.append([vis[0][0], 0, 0])
		heapq.heapify(q)
		while q:
			k = heapq.heappop(q)
			weight = k[0]
			u = k[1]
			v = k[2]
			if u == n - 1 and v == n - 1:
				return weight
			for (i, j) in [(1, 0), (0, 1), (0, -1), (-1, 0)]:
				nr = i + u
				nc = j + v
				if nr >= 0 and nr < n and (nc >= 0) and (nc < n):
					if vis[nr][nc] > grid[nr][nc] + k[0]:
						vis[nr][nc] = grid[nr][nc] + k[0]
						heapq.heappush(q, [vis[nr][nc], nr, nc])


import heapq

class Solution:

	def minimumCostPath(self, grid):
		n = len(grid)
		m = len(grid[0])
		dist = [[float('inf') for i in range(m)] for j in range(n)]
		vis = [[0 for i in range(m)] for j in range(n)]
		minheap = [(grid[0][0], 0, 0)]
		l = [[-1, 0], [0, -1], [1, 0], [0, 1]]
		vis[0][0] = 1
		dist[0][0] = 0
		while minheap:
			(cost, row, col) = heapq.heappop(minheap)
			vis[row][col] = 1
			for (i, j) in l:
				nrow = row + i
				ncol = col + j
				if nrow >= 0 and nrow < n and (ncol >= 0) and (ncol < m) and (not vis[nrow][ncol]) and (cost + grid[nrow][ncol] < dist[nrow][ncol]):
					if row == n - 1 and col == n - 1:
						return dist[-1][-1]
					vis[nrow][ncol] = 1
					dist[nrow][ncol] = cost + grid[nrow][ncol]
					heapq.heappush(minheap, (dist[nrow][ncol], nrow, ncol))
		return dist[n - 1][n - 1]


class Solution:

	def minimumCostPath(self, grid):
		import heapq
		n = len(grid)
		mat = [[100000000000000 for i in range(len(grid))] for i in range(len(grid))]
		mat[0][0] = grid[0][0]
		st = []
		st.append([mat[0][0], 0, 0])
		while len(st) > 0:
			(val, x, y) = heapq.heappop(st)
			if x + 1 < n and mat[x + 1][y] > grid[x + 1][y] + val:
				mat[x + 1][y] = grid[x + 1][y] + val
				tv = mat[x + 1][y]
				heapq.heappush(st, (tv, x + 1, y))
			if x - 1 >= 0 and mat[x - 1][y] > grid[x - 1][y] + val:
				mat[x - 1][y] = grid[x - 1][y] + val
				tv = mat[x - 1][y]
				heapq.heappush(st, (tv, x - 1, y))
			if y + 1 < n and mat[x][y + 1] > grid[x][y + 1] + val:
				mat[x][y + 1] = grid[x][y + 1] + val
				tv = mat[x][y + 1]
				heapq.heappush(st, (tv, x, y + 1))
			if y - 1 >= 0 and mat[x][y - 1] > grid[x][y - 1] + val:
				mat[x][y - 1] = grid[x][y - 1] + val
				tv = mat[x][y - 1]
				heapq.heappush(st, (tv, x, y - 1))
		return mat[n - 1][n - 1]


from functools import cmp_to_key
import heapq
ROW = 5
COL = 5

def mycmp(a, b):
	if a.distance == b.distance:
		if a.x != b.x:
			return a.x - b.x
		else:
			return a.y - b.y
	return a.distance - b.distance

class cell:

	def __init__(self, x, y, distance):
		self.x = x
		self.y = y
		self.distance = distance

def isInsideGrid(i, j):
	return i >= 0 and i < ROW and (j >= 0) and (j < COL)

def shortest(grid, row, col):
	dis = [[0 for i in range(col)] for j in range(row)]
	for i in range(row):
		for j in range(col):
			dis[i][j] = 1000000000
	dx = [-1, 0, 1, 0]
	dy = [0, 1, 0, -1]
	st = []
	heapq.heappush(st, (0, 0, 0))
	dis[0][0] = grid[0][0]
	while len(st) != 0:
		k = heapq.heappop(st)
		for i in range(4):
			x = k[1] + dx[i]
			y = k[2] + dy[i]
			if isInsideGrid(x, y) == 0:
				continue
			if dis[x][y] > dis[k[1]][k[2]] + grid[x][y]:
				dis[x][y] = dis[k[1]][k[2]] + grid[x][y]
				heapq.heappush(st, (dis[x][y], x, y))
	return dis[row - 1][col - 1]

class Solution:

	def minimumCostPath(self, grid):
		global ROW, COL
		ROW = len(grid)
		COL = len(grid[0])
		return shortest(grid, ROW, COL)


import heapq

class Solution:

	def minimumCostPath(self, grid):
		(m, n) = (len(grid), len(grid[0]))
		heap = [(grid[0][0], 0, 0)]
		dist = [[float('inf') for j in range(n)] for i in range(m)]
		dist[0][0] = grid[0][0]
		while heap:
			(curr_dist, i, j) = heapq.heappop(heap)
			if i == m - 1 and j == n - 1:
				return curr_dist
			for (x, y) in [(i - 1, j), (i + 1, j), (i, j - 1), (i, j + 1)]:
				if 0 <= x < m and 0 <= y < n and (dist[x][y] > curr_dist + grid[x][y]):
					dist[x][y] = curr_dist + grid[x][y]
					heapq.heappush(heap, (dist[x][y], x, y))
		return -1


import heapq as hq

class Solution:

	def minimumCostPath(self, grid):
		(m, n) = (len(grid), len(grid[0]))
		(que, visited) = ([], set([(0, 0)]))
		hq.heappush(que, (grid[0][0], 0, 0))
		while que:
			(curr_cost, ci, cj) = hq.heappop(que)
			if ci == m - 1 and cj == n - 1:
				return curr_cost
			for (ni, nj) in self.get_nbrs(ci, cj, m, n):
				new_cost = curr_cost + grid[ni][nj]
				if (ni, nj) not in visited:
					hq.heappush(que, (new_cost, ni, nj))
					visited.add((ni, nj))

	def get_nbrs(self, ci, cj, m, n):
		res = []
		for (di, dj) in [(-1, 0), (0, 1), (1, 0), (0, -1)]:
			ni = ci + di
			nj = cj + dj
			if 0 <= ni < m and 0 <= nj < n:
				res.append((ni, nj))
		return res


from heapq import heapify, heappop, heappush

def dijkstras(grid):
	n = len(grid)
	visited = set()
	visited.add((0, 0))
	heap = [(grid[0][0], 0, 0)]
	heapify(heap)
	while heap:
		(val, i, j) = heappop(heap)
		if (i, j) == (n - 1, n - 1):
			return val
		directions = [(0, 1), (1, 0), (-1, 0), (0, -1)]
		for (r, c) in directions:
			row = i + r
			col = j + c
			if row in range(n) and col in range(n) and ((row, col) not in visited):
				heappush(heap, (val + grid[row][col], row, col))
				visited.add((row, col))

class Solution:

	def minimumCostPath(self, grid):
		return dijkstras(grid)


from queue import Queue
from heapq import heappush, heappop

class Solution:

	def minimumCostPath(self, grid):
		moves = [(0, 1), (0, -1), (1, 0), (-1, 0)]
		vis = [[False] * len(grid) for _ in range(len(grid[0]))]
		dist = [[float('inf')] * len(grid) for _ in range(len(grid[0]))]
		dist[0][0] = 0
		pq = [(grid[0][0], 0, 0)]
		while pq:
			(d, i, j) = heappop(pq)
			for move in moves:
				(mi, mj) = (i + move[0], j + move[1])
				if 0 <= mi < len(grid) and 0 <= mj < len(grid[0]):
					if dist[mi][mj] > d + grid[mi][mj]:
						dist[mi][mj] = d + grid[mi][mj]
						heappush(pq, (dist[mi][mj], mi, mj))
		return dist[-1][-1]


import heapq
from collections import deque

class Solution:

	def minimumCostPath(self, grid):
		return f(grid)
import heapq

def f(grid):
	rows_n = len(grid)
	cols_n = len(grid[0])
	dist = grid[rows_n - 1][cols_n - 1]
	q = [(dist, rows_n - 1, cols_n - 1)]
	dists = [[1000000] * cols_n for _ in range(rows_n)]
	while q:
		top = heapq.heappop(q)
		(top_dist, row, col) = top
		steps = [(row, col + 1), (row, col - 1), (row + 1, col), (row - 1, col)]
		for (nrow, ncol) in steps:
			if 0 <= nrow < rows_n and 0 <= ncol < cols_n:
				dist = grid[nrow][ncol] + top_dist
				if dist < dists[nrow][ncol]:
					dists[nrow][ncol] = dist
					heapq.heappush(q, (dist, nrow, ncol))
	return dists[0][0]


import heapq

class Solution:

	def dijkstra(self, grid):
		rows = len(grid)
		if rows == 0:
			return -1
		cols = len(grid[0])
		dir = [(-1, 0), (0, -1), (1, 0), (0, 1)]
		cost = [[float('inf') for i in range(cols)] for i in range(rows)]
		cost[0][0] = grid[0][0]
		min_heap = []
		heapq.heappush(min_heap, (cost[0][0], 0, 0))
		while min_heap:
			(cost_so_far, i, j) = heapq.heappop(min_heap)
			for (di, dj) in dir:
				(new_i, new_j) = (i + di, j + dj)
				if new_i >= 0 and new_j >= 0 and (new_i < rows) and (new_j < cols) and (cost[new_i][new_j] > cost_so_far + grid[new_i][new_j]):
					cost[new_i][new_j] = cost_so_far + grid[new_i][new_j]
					heapq.heappush(min_heap, (cost[new_i][new_j], new_i, new_j))
		return cost[rows - 1][cols - 1]

	def minimumCostPath(self, grid):
		return self.dijkstra(grid)


from heapq import heappush, heappop

class Solution:

	def get_only_right_down_path_min_sum(self, grid):
		(row, col) = (len(grid), len(grid[0]))
		dp = [[0 for i in range(col)] for j in range(row)]
		dp[0][0] = grid[0][0]
		for i in range(1, row):
			dp[i][0] = dp[i - 1][0] + grid[i][0]
		for j in range(1, col):
			dp[0][j] = dp[0][j - 1] + grid[0][j]
		for i in range(1, row):
			for j in range(1, col):
				dp[i][j] = min(dp[i - 1][j - 1], dp[i - 1][j], dp[i][j - 1]) + grid[i][j]
		return dp[row - 1][col - 1]

	def neighbour(self, i, j, row, col):
		for (nr, nc) in ((i + 1, j), (i - 1, j), (i, j + 1), (i, j - 1)):
			if 0 <= nr < row and 0 <= nc < col:
				yield (nr, nc)

	def minimumCostPath(self, grid):
		(row, col) = (len(grid), len(grid))
		inf = float('inf')
		dp = [[inf for i in range(col)] for j in range(row)]
		dp[0][0] = grid[0][0]
		min_heap = []
		heappush(min_heap, (dp[0][0], 0, 0))
		while min_heap:
			(curr_cost, i, j) = heappop(min_heap)
			for (nr, nc) in self.neighbour(i, j, row, col):
				if dp[nr][nc] > dp[i][j] + grid[nr][nc]:
					dp[nr][nc] = dp[i][j] + grid[nr][nc]
					heappush(min_heap, (dp[nr][nc], nr, nc))
		return dp[row - 1][col - 1]


import heapq as heap

class Solution:

	def isValid(self, i, j, n):
		return 0 <= i < n and 0 <= j < n

	def minimumCostPath(self, grid):
		nodes = []
		visited = []
		cost = []
		movements = [[0, -1], [0, 1], [-1, 0], [1, 0]]
		for i in range(0, len(grid)):
			cost.append(len(grid) * [float('inf')])
			visited.append(len(grid) * [False])
		cost[0][0] = grid[0][0]
		heap.heappush(nodes, [cost[0][0], [0, 0]])
		while nodes:
			cur_v = heap.heappop(nodes)
			cx = cur_v[1][0]
			cy = cur_v[1][1]
			if visited[cx][cy]:
				continue
			visited[cx][cy] = True
			for movement in movements:
				nx = cx + movement[0]
				ny = cy + movement[1]
				if self.isValid(nx, ny, len(grid)):
					if grid[nx][ny] + cost[cx][cy] < cost[nx][ny]:
						cost[nx][ny] = cost[cx][cy] + grid[nx][ny]
						heap.heappush(nodes, [cost[nx][ny], [nx, ny]])
		return cost[len(grid) - 1][len(grid) - 1]


import heapq

class Solution:

	def minimumCostPath(self, grid):
		heap = [(grid[0][0], 0, 0)]
		dx = [-1, 1, 0, 0]
		dy = [0, 0, 1, -1]
		n = len(grid)
		m = len(grid[0])
		cost = [[float('inf') for _ in range(m)] for _ in range(n)]
		cost[0][0] = grid[0][0]
		while heap:
			(a, b, c) = heapq.heappop(heap)
			for i in range(4):
				x = b + dx[i]
				y = c + dy[i]
				if x < 0 or y < 0 or x >= n or (y >= m):
					continue
				if cost[x][y] > a + grid[x][y]:
					cost[x][y] = a + grid[x][y]
					heapq.heappush(heap, (cost[x][y], x, y))
		return cost[n - 1][m - 1]


from queue import PriorityQueue

class Solution:

	def isvalid(self, i, j, n, m):
		return i >= 0 and i < n and (j >= 0) and (j < m)

	def minimumCostPath(self, grid):
		(n, m) = (len(grid), len(grid[0]))
		dist = [[float('inf') for _ in range(m)] for _ in range(n)]
		dist[0][0] = grid[0][0]
		vis = [[0 for _ in range(m)] for _ in range(n)]
		pq = PriorityQueue()
		pq.put((grid[0][0], (0, 0)))
		x = [0, 0, -1, 1]
		y = [-1, 1, 0, 0]
		while not pq.empty():
			el = pq.get()
			d = el[0]
			(i, j) = (el[1][0], el[1][1])
			if i == n - 1 and j == m - 1:
				return d
			vis[i][j] = 1
			for k in range(4):
				if self.isvalid(i + x[k], j + y[k], n, m) and vis[i + x[k]][j + y[k]] == 0 and (dist[i][j] + grid[i + x[k]][j + y[k]] < dist[i + x[k]][j + y[k]]):
					dist[i + x[k]][j + y[k]] = dist[i][j] + grid[i + x[k]][j + y[k]]
					pq.put((dist[i + x[k]][j + y[k]], (i + x[k], j + y[k])))
		return dist[n - 1][m - 1]


import heapq

class Solution:

	def minimumCostPath(self, grid):

		def is_safe(i, j, V):
			if i >= 0 and j >= 0 and (i < V) and (j < V):
				return True
			return False
		V = len(grid)
		inf = 4294967295
		pq = []
		dist = [[inf for _ in range(V)] for _ in range(V)]
		dist[0][0] = grid[0][0]
		heapq.heappush(pq, (dist[0][0], 0, 0))
		directions = [(-1, 0), (0, 1), (1, 0), (0, -1)]
		while len(pq) > 0:
			(_, i, j) = heapq.heappop(pq)
			for k in range(4):
				(_i, _j) = (i + directions[k][0], j + directions[k][1])
				if is_safe(_i, _j, V) and dist[_i][_j] > dist[i][j] + grid[_i][_j]:
					dist[_i][_j] = dist[i][j] + grid[_i][_j]
					heapq.heappush(pq, (dist[_i][_j], _i, _j))
		return dist[V - 1][V - 1]


import heapq
from sys import maxsize

class Solution:

	def minimumCostPath(self, grid):
		distance = [[maxsize for j in range(len(grid[0]))] for i in range(len(grid))]
		path = [[None for j in range(len(grid[0]))] for i in range(len(grid))]
		distance[0][0] = grid[0][0]
		directions = [(0, 1), (0, -1), (1, 0), (-1, 0)]
		queue = list()
		queue.append((distance[0][0], (0, 0)))
		while queue:
			(dist, cell) = heapq.heappop(queue)
			(row, col) = (cell[0], cell[1])
			for i in directions:
				(nr, nc) = (row + i[0], col + i[1])
				if nr < 0 or nr >= len(grid) or nc < 0 or (nc >= len(grid[0])):
					continue
				newDistance = dist + grid[nr][nc]
				if newDistance < distance[nr][nc]:
					distance[nr][nc] = newDistance
					heapq.heappush(queue, (newDistance, (nr, nc)))
					path[nr][nc] = (row, col)
		return distance[-1][-1]


import sys
from heapq import heapify, heappush, heappop

class Cell:

	def __init__(self, x, y, distance):
		self.x = x
		self.y = y
		self.distance = distance

class Solution:

	def mycmp(self, a, b):
		if a.distance == b.distance:
			if a.x != b.x:
				return a.x - b.x
			else:
				return a.y - b.y
		return a.distance - b.distance

	def shortest(self, grid, row, col):
		dis = [[sys.maxsize] * col for j in range(row)]
		dx = [-1, 0, 1, 0]
		dy = [0, 1, 0, -1]
		st = []
		st.append(Cell(0, 0, 0))
		dis[0][0] = grid[0][0]
		while len(st) != 0:
			k = st[0]
			st = st[1:]
			for i in range(4):
				x = k.x + dx[i]
				y = k.y + dy[i]
				if x < 0 or y < 0 or x >= row or (y >= col):
					continue
				if dis[x][y] > dis[k.x][k.y] + grid[x][y]:
					dis[x][y] = dis[k.x][k.y] + grid[x][y]
					st.append(Cell(x, y, dis[x][y]))
			st.sort(key=cmp_to_key(self.mycmp))
		return dis[row - 1][col - 1]

	def minimumCostPath(self, grid):
		n = len(grid)
		heap = [(grid[0][0], 0, 0)]
		heapify(heap)
		v = set((0, 0))
		while heap:
			(val, i, j) = heappop(heap)
			if i == n - 1 and j == n - 1:
				return val
			directions = [(0, 1), (1, 0), (-1, 0), (0, -1)]
			for (r, c) in directions:
				row = i + r
				col = j + c
				if row in range(n) and col in range(n) and ((row, col) not in v):
					heappush(heap, (val + grid[row][col], row, col))
					v.add((row, col))
		return val


import heapq as hq

class Solution:

	def minimumCostPath(self, grid):
		(m, n) = (len(grid), len(grid[0]))
		dp = [[float('inf') for i in range(m)] for _ in range(n)]
		dp[0][0] = grid[0][0]
		s = [0, 0]
		q = []
		hq.heappush(q, (dp[0][0], s))
		while q:
			(d_v, v) = hq.heappop(q)
			for (dr, dc) in {(-1, 0), (0, -1), (0, 1), (1, 0)}:
				(row, col) = (v[0] + dr, v[1] + dc)
				if row in range(m) and col in range(n) and (dp[row][col] > dp[v[0]][v[1]] + grid[row][col]):
					dp[row][col] = dp[v[0]][v[1]] + grid[row][col]
					hq.heappush(q, (dp[row][col], [row, col]))
		return dp[m - 1][n - 1]


import heapq

def isInside(i, j, n, m):
	if i >= 0 and i < n and (j >= 0) and (j < m):
		return True
	return False

def getAvailableNeighbors(i, j, n, m):
	dx = [-1, 1, 0, 0]
	dy = [0, 0, 1, -1]
	avail = []
	for w in range(len(dy)):
		x = i + dx[w]
		y = j + dy[w]
		if isInside(x, y, n, m):
			avail.append((x, y))
	return avail

class Solution:

	def minimumCostPath(self, grid):
		n = len(grid)
		heap = []
		dist = [[100000000.0] * n for i in range(n)]
		dist[0][0] = grid[0][0]
		heapq.heapify(heap)
		heapq.heappush(heap, (grid[0][0], 0, 0))
		while heap:
			current = heapq.heappop(heap)
			cost = current[0]
			x = current[1]
			y = current[2]
			if (x, y) == (n - 1, n - 1):
				return cost
			neighbors = getAvailableNeighbors(x, y, n, n)
			for neigh in neighbors:
				if grid[neigh[0]][neigh[1]] + cost < dist[neigh[0]][neigh[1]]:
					dist[neigh[0]][neigh[1]] = grid[neigh[0]][neigh[1]] + cost
					heapq.heappush(heap, (dist[neigh[0]][neigh[1]], neigh[0], neigh[1]))


import heapq

class Solution:

	def minimumCostPath(self, grid):
		n = len(grid)
		m = len(grid[0])
		heap = []
		dist = [[float('inf')] * m for i in range(n)]
		dist[0][0] = grid[0][0]
		heapq.heappush(heap, (grid[0][0], [0, 0]))
		dx = [-1, 0, 1, 0]
		dy = [0, 1, 0, -1]
		while heap:
			(cost, pair) = heapq.heappop(heap)
			r = pair[0]
			c = pair[1]
			if r == n - 1 and c == m - 1:
				return cost
			for i in range(4):
				newr = dx[i] + r
				newc = dy[i] + c
				if newr >= 0 and newr < n and (newc >= 0) and (newc < m) and (grid[newr][newc] + cost < dist[newr][newc]):
					dist[newr][newc] = grid[newr][newc] + cost
					heapq.heappush(heap, (dist[newr][newc], [newr, newc]))