众所周知，榔头可以砸死太极。 身为一个太极爱好者，fish布下了一个八卦阵。这个阵可以认为是一个n个点，m条边的有向图。每条边i有一个困难度a[i]。每个点u有八个状态：b[u][1],b[u][2],...,b[u][8]，这八个状态为均[1,8]之间的整数(不一定是排列)，在第i秒中，u的状态为b[u][(i-1)%8+1]。对于任意两个状态i,j都存在一个复杂度c[i][j]。 现在bx2k想从1号点走到n号点，他在第一秒开始时在一号点，每次他可以用一秒从当前点u走到另一个有边相连的点v。也就是说，bx2k会在第一秒内走过第一条边，在第二秒内走过第二条边……由于fish的布阵极其巧妙，bx2k必须砸出一些榔头才能走过一条边。若bx2k在第i秒通过第j条边从点u走到点v，他需要砸出a[j]+c[b[u][(i-1)%8+1]][b[v][(i-1)%8+1]]个榔头。 bx2k非常想进这个八卦阵玩，但他又不想带太多的榔头。所以bx2k希望你能帮他算出至少要多少个榔头才能从点1走到点n。

第一行包含两个正整数n,m。 接下来八行，每行包含八个正整数，其中的第i行的第j个整数表示c[i][j]。 接下来n行，每行包含八个正整数，其中第i行的第j个整数表示b[i][j]。 接下来m行，每行包含三个正整数u,v,a[i]，表示有一条从u到v，困难度为a[i]的边。

第一行包含一个正整数，表示至少需要多少个榔头，数据保证有解。

3 3
0 1 0 0 0 0 0 11
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 11 0 0 0 0 0
0 0 0 0 0 0 0 0
1 2 3 4 5 6 7 8
8 7 6 5 4 3 2 1
2 3 3 3 3 3 3 3
1 2 100
2 3 100
1 3 233

222

【样例说明1】
有两种方案：
1.直接从1->3，费用为a[1]+c[1][2]=233+1=234。
2.1->2->3，费用为(a[2]+c[1][8])+(a[3]+c[7][3])=(100+11)+(100+11)=222。