Minimum Travel Time

You are given a 2D grid of size \(n \times m\) where each cell contains an integer representing the time required to pass through that cell. Your task is to compute the minimum time required to travel from the top-left corner (i.e., cell \((0,0)\)) to the bottom-right corner (i.e., cell \((n-1, m-1)\)). You can only move to adjacent cells in four directions: up, down, left, and right.

The problem can be modeled as finding the shortest path in a weighted grid. A common solution is to implement Dijkstra's algorithm. Make sure your solution reads input from stdin and prints the answer to stdout.

inputFormat

The input is given via stdin as follows:

n m
row1_value1 row1_value2 ... row1_value_m
row2_value1 row2_value2 ... row2_value_m
... 
rown_value1 rown_value2 ... rown_value_m

Where:

• \(n\) is the number of rows.
• \(m\) is the number of columns.
• The following \(n\) lines each contain \(m\) integers representing the grid.

outputFormat

Output a single integer to stdout representing the minimum travel time from cell \((0,0)\) to cell \((n-1, m-1)\).

3 3
1 3 1
1 5 1
4 2 1

7