/* package whatever; // don't place package name! */
 
import java.util.*;
import java.lang.*;
import java.io.*;
class Path
{
    int x; int y; int z;
    //z is the minimum distance required to reach grid element at index(x,y)
    Path(int x, int y,int z)
    {
        this.x=x;
        this.y=y;
        this.z=z;
    }
}
class Solution {
    public int minPathSum(int[][] grid) {
        int row=grid.length;
        int col=grid[0].length;
        boolean[][] visited=new boolean[row][col];
        int []dx={1,0};
        int []dy={0,1};
        PriorityQueue <Path> queue=new PriorityQueue<Path>((e,f)->(e.z-f.z));
        queue.offer(new Path(0,0,grid[0][0]));
        while(!queue.isEmpty())
        {
            Path temp=queue.poll();
 
            if(temp.x==row-1&&temp.y==col-1)
            return temp.z;
            for(int i=0;i<2;i++)
            {
                int a=temp.x+dx[i];
                int b=temp.y+dy[i];
                if(a<0||a>=row||b<0||b>=col||visited[a][b]==true)
                continue;
                visited[a][b]=true;
                queue.offer(new Path(a,b,temp.z+grid[a][b]));
            }
        }
        return -1;
    }
}

LyogcGFja2FnZSB3aGF0ZXZlcjsgLy8gZG9uJ3QgcGxhY2UgcGFja2FnZSBuYW1lISAqLwoKaW1wb3J0IGphdmEudXRpbC4qOwppbXBvcnQgamF2YS5sYW5nLio7CmltcG9ydCBqYXZhLmlvLio7CmNsYXNzIFBhdGgKewogICAgaW50IHg7IGludCB5OyBpbnQgejsKICAgIC8veiBpcyB0aGUgbWluaW11bSBkaXN0YW5jZSByZXF1aXJlZCB0byByZWFjaCBncmlkIGVsZW1lbnQgYXQgaW5kZXgoeCx5KQogICAgUGF0aChpbnQgeCwgaW50IHksaW50IHopCiAgICB7CiAgICAgICAgdGhpcy54PXg7CiAgICAgICAgdGhpcy55PXk7CiAgICAgICAgdGhpcy56PXo7CiAgICB9Cn0KY2xhc3MgU29sdXRpb24gewogICAgcHVibGljIGludCBtaW5QYXRoU3VtKGludFtdW10gZ3JpZCkgewogICAgICAgIGludCByb3c9Z3JpZC5sZW5ndGg7CiAgICAgICAgaW50IGNvbD1ncmlkWzBdLmxlbmd0aDsKICAgICAgICBib29sZWFuW11bXSB2aXNpdGVkPW5ldyBib29sZWFuW3Jvd11bY29sXTsKICAgICAgICBpbnQgW11keD17MSwwfTsKICAgICAgICBpbnQgW11keT17MCwxfTsKICAgICAgICBQcmlvcml0eVF1ZXVlIDxQYXRoPiBxdWV1ZT1uZXcgUHJpb3JpdHlRdWV1ZTxQYXRoPigoZSxmKS0+KGUuei1mLnopKTsKICAgICAgICBxdWV1ZS5vZmZlcihuZXcgUGF0aCgwLDAsZ3JpZFswXVswXSkpOwogICAgICAgIHdoaWxlKCFxdWV1ZS5pc0VtcHR5KCkpCiAgICAgICAgewogICAgICAgICAgICBQYXRoIHRlbXA9cXVldWUucG9sbCgpOwogICAgICAgICAgICAKICAgICAgICAgICAgaWYodGVtcC54PT1yb3ctMSYmdGVtcC55PT1jb2wtMSkKICAgICAgICAgICAgcmV0dXJuIHRlbXAuejsKICAgICAgICAgICAgZm9yKGludCBpPTA7aTwyO2krKykKICAgICAgICAgICAgewogICAgICAgICAgICAgICAgaW50IGE9dGVtcC54K2R4W2ldOwogICAgICAgICAgICAgICAgaW50IGI9dGVtcC55K2R5W2ldOwogICAgICAgICAgICAgICAgaWYoYTwwfHxhPj1yb3d8fGI8MHx8Yj49Y29sfHx2aXNpdGVkW2FdW2JdPT10cnVlKQogICAgICAgICAgICAgICAgY29udGludWU7CiAgICAgICAgICAgICAgICB2aXNpdGVkW2FdW2JdPXRydWU7CiAgICAgICAgICAgICAgICBxdWV1ZS5vZmZlcihuZXcgUGF0aChhLGIsdGVtcC56K2dyaWRbYV1bYl0pKTsKICAgICAgICAgICAgfQogICAgICAgIH0KICAgICAgICByZXR1cm4gLTE7CiAgICB9Cn0=