This is a fairly classic problem, posed for homework, etc. (In fact, it is the basis for at least one Project Euler problem, easily solved.)
The trick is, if you start at the top right cell, the cost to get to that point is simple. Now, you can simply compute the cost to go to ANY of the three neighbors of that cell, left, down, or left/down.
Store those costs in the new matrix, in the corresponding cells, as long as the new cost to get to that cell is less than the cost to get to it from any of its neighbors.
Now, you have three new start points. For each of them, you can compute the cost to get to any of the three neighbors of that cell. You will just work down the matrix. The time required will not be large, since you keep a record of the cost required to get to each cell from its neighbors. What you do not need to do is compute all possible paths, because you are computing at each step, the cheapest cost to get to the front that you have examined so far.
As I said, the idea is simple, but you need to avoid brute force, computing all paths, as that would quickly become uncountably huge. And that is why they posed it as one of the Project Euler problems. (Admittedly, an early, easy one.)