CF187B.AlgoRace

PMP is getting a warrior. He is practicing a lot, but the results are not acceptable yet. This time instead of programming contests, he decided to compete in a car racing to increase the spirit of victory. He decides to choose a competition that also exhibits algorithmic features.

AlgoRace is a special league of car racing where different teams compete in a country of n cities. Cities are numbered 1 through n. Every two distinct cities in the country are connected with one bidirectional road. Each competing team should introduce one driver and a set of cars.

The competition is held in r rounds. In i-th round, drivers will start at city s__i and finish at city t__i. Drivers are allowed to change their cars at most k__i times. Changing cars can take place in any city in no time. One car can be used multiple times in one round, but total number of changes should not exceed k__i. Drivers can freely choose their path to destination.

PMP has prepared m type of purpose-built cars. Beside for PMP’s driving skills, depending on properties of the car and the road, a car traverses each road in each direction in different times.

PMP Warriors wants to devise best strategies of choosing car and roads in each round to maximize the chance of winning the cup. For each round they want to find the minimum time required to finish it.

PMP 正在招募一名战士。他进行了大量训练，但目前成果尚不理想。这一次，他决定不再参加编程竞赛，而是转战赛车比赛，以提升胜利的斗志。他打算选择一项同时兼具算法特征的赛事。

AlgoRace 是一个特殊的赛车联赛，在一个拥有 $n$ 座城市的国家中举行。城市编号为 $1$ 至 $n$。该国中任意两座不同的城市之间都由一条双向道路相连。每支参赛队需派出一名车手及一套赛车。

比赛共进行 $r$ 轮。在第 $i$ 轮中，车手须从城市 $s_i$ 出发，抵达城市 $t_i$。车手在该轮中最多可更换赛车 $k_i$ 次；换车可在任意城市即时完成（耗时为零）。同一辆赛车可在一轮中多次使用，但整轮中换车总次数不得超过 $k_i$。车手可自由选择通往终点的路径。

PMP 已准备了 $m$ 种专用赛车。除 PMP 自身的驾驶技术外，由于赛车性能与道路特性的差异，每种赛车在每条道路的两个方向上行驶所需时间各不相同。

PMP 战士队希望为每一轮比赛制定最优策略，以选择合适的赛车与行驶路径，从而最大化夺冠概率。对于每一轮，他们均需计算出完成该轮所需的最短时间。

The first line contains three space-separated integers n, m, r (2 ≤ n ≤ 60, 1 ≤ m ≤ 60, 1 ≤ r ≤ 105) — the number of cities, the number of different types of cars and the number of rounds in the competition, correspondingly.

Next m sets of n × n matrices of integers between 0 to 106 (inclusive) will follow — describing the time one car requires to traverse different roads. The k-th integer in j-th line of the i-th set is the time that i-th car requires to traverse the road from j-th city to k-th city. These matrices are not necessarily symmetric, but their diagonal is always zero.

Next r lines contain description of the rounds. The i-th of these lines contains space-separated integers s__i, t__i, k__i (1 ≤ s__i, t__i ≤ n, s__i ≠ t__i, 0 ≤ k__i ≤ 1000) — the number of starting city, finishing city and the number of possible car changes in i-th round, correspondingly.

第一行包含三个以空格分隔的整数 $n$、$m$、$r$（$2 \leq n \leq 60$，$1 \leq m \leq 60$，$1 \leq r \leq 10^5$），分别表示城市数量、汽车种类数量以及比赛轮数。

接下来是 $m$ 组 $n \times n$ 的整数矩阵，每个矩阵中的整数取值范围为 $0$ 到 $10^6$（含端点），用于描述各类汽车在不同道路间的行驶时间。第 $i$ 组矩阵中第 $j$ 行第 $k$ 列的整数，表示第 $i$ 类汽车从第 $j$ 个城市行驶到第 $k$ 个城市所需的时间。这些矩阵未必对称，但其主对角线元素恒为 $0$。

接下来 $r$ 行描述各轮比赛。其中第 $i$ 行包含三个以空格分隔的整数 $s_i$、$t_i$、$k_i$（$1 \leq s_i, t_i \leq n$，$s_i \neq t_i$，$0 \leq k_i \leq 1000$），分别表示第 $i$ 轮的出发城市编号、到达城市编号以及该轮允许的换车次数。

For each round you should print the minimum required time to complete the round in a single line.

每轮输出一行，表示完成该轮所需的最少时间。

In the first sample, in all rounds PMP goes from city #1 to city #2, then city #3 and finally city #4. But the sequences of types of the cars he uses are (1, 2, 1) in the first round and (1, 2, 2) in the second round. In the third round, although he can change his car three times, he uses the same strategy as the first round which only needs two car changes.

在第一个样例中，PMP 在所有轮次中均从城市 #1 出发，依次经过城市 #2、城市 #3，最终到达城市 #4。但他所用车辆类型的序列在第一轮为 $(1, 2, 1)$，在第二轮为 $(1, 2, 2)$。在第三轮中，尽管他最多可更换三次车辆，但他仍采用与第一轮相同的策略，该策略仅需两次车辆更换。