题目描述

给定一个包含 $n$ 个点的图 $G$，用邻接矩阵 $A_{i,j}$ 表示，其中 $A_{i,j} = 0$ 表示无边，$A_{i,j} > 0$ 表示有边，$A_{i,j}$ 的值为边权。

给定 $m$ 次询问，每次询问你需要找出从 $a_i$ 到 $b_i$ 恰好经过 $c_i$ 条边的边权和最小的路径。对于每次询问，你可以选择某一条边，将其中的一次经过的边权整除 $2$（如果多次经过一条边，只有一次整除 $2$，其它次按原边权计算）。

输入格式

输入的第一行包含一个整数 $n$。

接下来 $n$ 行，每行包含 $n$ 个整数，表示邻接矩阵 $A_{i,j}$，相邻整数之间使用一个空格分隔。

接下来一行包含一个整数 $m$。

接下来 $m$ 行，每行包含 3 个整数 $a_i, b_i, c_i$ 表示一次询问，相邻整数之间使用一个空格分隔。

输出格式

输出 $m$ 行，每行包含一个整数依次表示每次询问的答案。如果有恰好经过 $c_i$ 条边的路径，输出路径的最小权值和。如果没有恰好经过 $c_i$ 条边的路径，输出 $-1$。

3
0 1 1
0 1 0
1 0 0
4
2 1 1
1 2 2
1 3 3
3 1 4

-1
1
2
-1

提示

评测用例规模与约定

• 对于 $40\%$ 的评测用例，$m = 1$，$c_i \leq 50$；
• 另有 $10\%$ 的评测用例，$m \leq 100$，$c_i \leq 50$；
• 另有 $20\%$ 的评测用例，$m = 1$，$c_i < 2^{24}$；
• 对于所有评测用例，$1 \leq n \leq 50$，$1 \leq m \leq 1000$，$1 \leq a_i, b_i \leq n$，$1 \leq c_i \leq 10^9$，$0 \leq A_{i,j} \leq 10^9$。