本题原为复仇者联盟排位赛#5 T5.

复仇者_bsa接受了一个挑战，只要走出一个迷宫，就可以获得一只蒟蒻的账号！但是当他进入迷宫内，傻眼了：这迷宫复杂至极，一眼望不到尽头。还好有场外援助cjdst，他细心地发现bsa所在的迷宫分成很多的小块，里面有一个个小房间：

有些块是比较标准的，相当于一个 $n\times m$ 的矩形，而且和标准迷宫差不多，bsa只能上下左右移动至附近的一格，但通过每个小房间的所需时间不同.

而有些块是不规则的，相当于一个有向图，经过相邻两个房间所需的时间长短不一，一个房间可能有非常多个出口，但也可能一个出口都没有，而且还不能保证如果能从 $A$ 房间到达 $B$ 房间，$B$ 房间就一定能返回 $A$ 房间.

现在，复仇者_bsa收到了他所在的这一块的信息，请你帮助他求出通过这一整块的最短时间.

第一行一个整数 $k$，表示bsa所在块的种类.

若 $k=1$，则该块是标准的矩形迷宫.
第二行两个正整数 $n,m$，表示矩形迷宫的长和宽.
第 $3\sim n+2$ 行，每行 $m$ 个正整数，表示迷宫对应房间的通过所需时间.
第 $n+3$ 行两个正整数 $x,y$，表示复仇者_bsa所在位置.出口在右下角.

若 $k=2$，则该块是不规则迷宫.
第二行两个正整数 $n,m$，表示共有 $n$ 个房间，$m$ 个出口，复仇者_bsa的位置是在 $1$ 号房间，该块的出口在 $n$ 号房间.
第 $3\sim m+2$ 行，每行 $3$ 个正整数 $A,B,C$，表示 $A$ 号房间有一个出口通向 $B$ 号房间，所需 $C$ 的时间.

一个整数，表示bsa通过该块的最短时间，若不能通过，输出-1.

对于 $100\%$ 的测试点，$1\le k\le2$.
当 $k=1$ 时，$1\le n,m\le10^3$，$1\le x\le m,1\le y\le n$，保证每个房间通过所需时间不超过 $10^3$.
当 $k=2$ 时，$1\le n\le10^5,1\le m\le3\times10^5$，保证从一个房间至相连的另一个房间所需时间不超过 $10^4$.

样例#1解释

一种可行的办法如下：

样例#2解释

按照红线走，所耗时间最短.

提示：可以参考走迷宫3，使用优先队列代替队列进行广搜.