题目背景

Jasonwei 在一个 $n$ 层的大楼里上班办公，大楼的第一层有 $n\times n$ 个房间，第二层有 $(n-1)\times(n-1)$ 个房间 $\cdots$ 最高层即大楼的第 $n$ 层有 $1$ 个房间。例如下图，为一个 $n=3$ 的大楼的俯视图。

题目描述

一开始 Jasonwei 所在的位置是大楼的第一层的第一行第一列的房间，Jasonwei 想要到最高层的那个房间的上面去看风景（因为原来的房间里面有苍蝇，影响了心情）。Jasonwei 每经过一个房间都需要时间，且他只能往上走，不能向下走，就是说 Jasonwei 只能到同层中与他所在房间相邻的房间去或者到上面一层中与他所在房间相邻的房间去。

但是这个大楼里还有 $m$ 个暗道，每个暗道都是从低层的某个房间到高层的某个房间里，走暗道也需要时间。

请你帮助 Jasonwei 求出到达大楼顶层所需要的最少时间。

输入格式

第 $1$ 行包含两个正整数 $n$ 和 $m$。
接下来 $n$ 部分，第 $k$ 部分包含 $n+1-k$ 行，每行 $n+1-k$ 个数，其中第 $i$ 行的第 $j$ 个数表示通过第 $i$ 行第 $j$ 列的房间需要的时间，为不超过的正整数。
接下来$m$行，每行七个正整数 $a,b,c,x,y,z,t$，表示从第 $a$ 层的第 $b$ 行第 $c$ 列的房间有暗道通到第 $x$ 层的第 $y$ 行第 $z$ 列的房间，且通过该暗道的时间为 $t$。

输出格式

输出共一行一个整数，即到达目的地最少需要的时间。

3 1
1 1 10
1 10 10
1 10 10
10 3
10 10
1
1 3 1 3 1 1 1

5

数据规模与约定

对于 $20\%$ 的数据： $1\le n\le10$，$0\le m\le 100$；
对于 $50\%$ 的数据： $1\le n\le 30$，$0\le m\le 200$；
对于 $100\%$ 的数据：$1\le n\le 100$，$0\le m\le 10^3$，$1\le t\le 10^4$，$1\le a<x\le n$，$1\le b,c\le n+1-a$；$1\le y,z\le n+1-x$。