Minimum Path Sum in a Grid

Given a grid of non-negative integers with dimensions (n \times m), find the minimum cost path from the top-left cell (i.e., cell ((0,0))) to the bottom-right cell (i.e., cell ((n-1, m-1))). The allowed moves are up, down, left, and right. The cost of a path is the sum of the values of all visited cells (including the starting and ending cells). It is guaranteed that a path always exists.

Note: The problem can be solved using Dijkstra's algorithm (or A* search) since all weights are non-negative.

inputFormat

The first line contains two integers (n) and (m), representing the number of rows and columns, respectively. This is followed by (n) lines, each containing (m) space-separated integers representing the grid.

outputFormat

Output a single integer: the minimum cost to traverse from the top-left cell to the bottom-right cell.## sample

3 3
1 3 1
1 5 1
4 2 1

7