现有一种格子迷宫，该迷宫由N行N列的格子构成。迷宫中有三种格子，第一种是墙壁，不能通过；第二种格子能正常通行，经过该格子可以到达与它相邻的上/下/左/右格子中；第三种格子除了具有第二种格子的功能外，它还具有“瞬间移动”功能，到达此格子后，可以选择是否瞬间被传送到给定的格子上。在一个由上述三种格子构成的迷宫中，给定起点和终点的位置，求从起点到达终点所需要的最小代价。

下图是一个3*3格子迷宫，该迷宫中2号格子具有的“瞬间移动”功能是能传送至8号格子，7号格子则是能传送至9号格子。





3*3迷宫示例



1 0(8) -1

2 1 2

0(9) 1 2



Input Descr iption





第一行：迷宫的规模N值 起点格子序号start 终点格子序号end



接下来的N*N行：依次按逐行扫描方式输入迷宫中序号为1至N*N的格子的代价值及跳转的格子序号M(如果有的话)。



Output Descr iption



输出从起点到达终点所需要的最小代价。这里需要注意的是，若从指定起点无法到达终点，则输出为INF(请在程序中宏定义为4字节int型变量表示的最大正数值，即为2147483647)。-Present a lattice maze, the labyrinth consists of a grid of N rows and N columns. There are three maze grid, the first one is a wall, you can not pass　the second grid normal passage through the lattice can be reached with its adjacent up/down/left/right grid　and the third grid in addition to a first two grid functions, it also has " teleport"　feature, this lattice arrive, you can choose whether a given moment is transferred to the lattice. In the maze of a grid consisting of the three, given a start and end location, find the minimum cost required　the beginning of the end arrives. The figure is a 3* 3 grid maze, the maze has a grid on the 2nd of " teleport"　feature is capable of transmitting to the 8th grid, the grid is capable of transmitting the 7th to the 9th grid. Labyrinth Example 3* 3 1 0 (8)-1 2 1 2 0 (9) 1 2 Input Descr iption First line: the value of the starting point of the maze lattice size N number start end end The next grid numbers N* N lines: followe