The Scylla is a quite important thing that Michael and his partners want to get. It is located in a building which belongs to the company. The company is a mysterious organization which affects economy, politics, science, war and so on. To destroy the company and save themselves, Michael must steal the Scylla. Through a long-time investigation, Michael knows that the Scylla is in a room on the top of the building. The Building is also unique, each layer is a square. Assume that it has N floors, the first floor has N*N rooms, the second floor has (N-1)*(N-1) rooms, and the top floor has only one room where Scylla was placed. (The building construction is like the schema below)
Michael has already numbered all the rooms with 3 numbers, Xi, Yi, Zi, Xi means the floor, Xi=1 means the first floor, Xi=N means the top floor, Yi means the row number of the room in a floor and Zi means the column number of the room. The plan Michael figures out is that: First, enter the room 1-1-1, then destroy the ceiling of the room to go upstairs, or open an door to enter the rooms beside the current one. Repeat it until he enters the room N-1-1 on the top floor, finally, destroy the ceiling of room N-1-1 to leave the building with Scylla. A helicopter will be there waiting for them. However, they should stay in every room they entered for some time to destroying the ceiling, open the door or find the tunnels (illustrated bellow), Michael already had the data Ai.
There are some tunnels which can be used by Michael. Each tunnel has only one entrance and one exit. These tunnels can help them go from the room with entrance to the room with exit directly, but it will take more time Ti to get through the tunnel. And each room can be entrance of 40 tunnels at most.
In the course of the theft of the Scylla, Michael can't go downstairs, or he will be caught by the people in the company!
Input
The input file will contain multiple test cases(<=20). In each case, first line is N, M. N means the height of the building and also the side length of the first floor. M means the number of tunnels. (0 <= N <= 100, 0 <= M <= 100) Following are N squares. The first square has N*N integers indicating the time they must stay in each room on the first floor. The second square has (N-1)*(N-1) integers indicating the time they must stay in each room on the second floor. ... And the Nth square has 1 integer means the time they must stay in the room on the top floor. (0 <= Ai <= 10000) Then M lines follow, every line has 7 integers: Xi1, Yi1, Zi1, Xi2, Yi2, Zi2, Ti. It means a tunnel from room Xi1-Yi1-Zi1 to room Xi2-Yi2-Zi2 with extra time Ti. (We assure that 1 <= Xi1, Yi1, Zi1, Xi2, Yi2, Zi2 <= N, Xi1 < Xi2, 0 <= Ti < 10000) After each case, there is a blank line.
Output
For each case, you should print a single line with a single integer, the least time to get the Scylla and leave the buiding.
Sample Input
3 1
6 1 3
2 1 4
3 2 5
4 5
3 9
2
1 3 3 2 1 1 1
3 1
6 1 3
2 1 4
3 2 5
4 5
3 9
2
1 1 1 3 1 1 1
Sample Output
12
9
