给定一个 $n$ 个点的有向图，点的编号为 $1 \sim n$，对于任意两个不同的点 $i \neq j$，$i$ 到 $j$ 都有一条边，边权为 $a_{i,j}$。

在接下来 $q$ 天，每天都会有一个节点 $p_i$ 在当天关闭，你需要给出这一天 $s_i$ 在不经过 $p_i$ 的前提下，到达 $t_i$ 的最短路径长度。

Input

第一行两个正整数 $n, q$ ($3 \leq n \leq 300, 1 \leq q \leq 5\times 10^5$) 表示有向图的节点数以及询问个数。

下面 $n$ 行，每行 $n$ 个整数，其中第 $i$ 行第 $j$ 个整数表示 $a_{i, j}$ ($0 \leq a_{i, j} \leq 10^{14}, a_{i, i}=0$)。

下面 $q$ 行，每行三个整数 $s_i, t_i, p_i$ ($1 \leq s_i, t_i, p_i \leq n$, $s_i, t_i, p_i$ 互不相同)，表示询问 $s_i$ 在不经过 $p_i$ 的前提下，到达 $t_i$ 的最短路径长度。

Output

一共 $q$ 行，每行一个整数表示答案。

Examples

Input

3 3
0 7 8
14 0 5
8 16 0
3 2 1
1 3 2
2 1 3

Output

16
8
14

Input

5 8
0 15 8 7 8
8 0 8 6 8
8 7 0 14 7
5 7 6 0 14
12 8 7 6 0
4 3 5
4 5 1
5 1 4
4 5 3
1 2 4
2 3 5
3 4 2
3 4 5

Output

6
13
12
13
15
8
13
13

Notes

对于 $30\%$ 的测试点： $n, q \leq 100$。

对于 $50\%$ 的测试点： $q \leq 1000$。

对于所有测试点：$1 \leq s_i, t_i, p_i \leq n \leq 300, 1 \leq q \leq 5\times 10^5, 0 \leq a_{i, j} \leq 10^{14}, \forall 1 \leq i \leq n: a_{i,i}=0$。