Minimum Cost Path in a Grid

You are given a grid of non-negative integers with n rows and m columns. Your task is to find a path from the top-left cell (i.e. cell at row 0, column 0) to the bottom-right cell (i.e. cell at row n-1, column m-1) such that the sum of the numbers along the path is minimized.

You can only move either right or down at any step. In case of ties when choosing the previous cell, you should prefer moving from the top. The answer should be the sequence of coordinates in order, where each coordinate is represented in the format (i,j) (without any spaces inside the parentheses) and consecutive coordinates are separated by a single space.

The cost of a path \(P\) is defined as \[ \text{cost}(P)=\sum_{(i,j)\in P} grid[i][j] \]

Input/Output Format: The input is read from standard input and the output should be written to standard output as described below.

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 integers separated by spaces representing the grid.

For example:

3 3
1 3 1
1 5 1
4 2 1

outputFormat

Print the minimum cost path from the top-left to the bottom-right cell. The path should be printed as a sequence of coordinates in the format (i,j), where i and j are the row and column indices respectively. Separate consecutive coordinates with a single space.

For the sample input above, the output should be:

(0,0) (0,1) (0,2) (1,2) (2,2)

## sample

3 3
1 3 1
1 5 1
4 2 1

(0,0) (0,1) (0,2) (1,2) (2,2)