给定一个 $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$。