#include <algorithm>
#include <array>
#include <cstdio>
#include <iostream>
#include <tuple>
#include <vector>

using namespace std;

constexpr int N = 303;
constexpr int Q = 514514;

class fastIn {
	private:
	
	char buf [1 << 20];
	char *p1 = buf;
	char *p2 = buf;
	
	inline char getch ();
	
	public:
	
	template <typename NumT>
	void read (NumT &num);
	
	template <typename NumT>
	fastIn& operator >> (NumT &num);
};

inline char fastIn::getch () {
	if (p1 == p2) {
		p1 = buf;
		p2 = buf + fread (buf, 1, 1 << 20, stdin);
		if (p1 == p2) {
			return EOF;
		}
	}
	return *p1++;
}

template <typename NumT>
void fastIn::read (NumT &num) {
	char ch = getch ();
	NumT op = 1;
	num = 0;
	
	while (ch < '0' || '9' < ch) {
		op = ((ch == '-') ? -1 : 1);
		ch = getch ();
	}
	while ('0' <= ch && ch <= '9') {
		num *= 10;
		num += (ch - '0');
		ch = getch ();
	}
	
	num *= op;
}

template <typename NumT>
fastIn& fastIn::operator >> (NumT &num) {
	read (num);
	return *this;
}

fastIn fin;

int n;
int q;
using arr = vector<vector<long long>>;
vector<tuple<int, int, int>> ques[N];
long long res[Q];

void solve (int l, int r, arr g) {
	if (l == r) {
		for (auto [s, t, i] : ques[l]) {
			res[i] = g[s][t];
		}
		return;
	}

	auto h = g;
	int mid = (l + r) / 2;

	for (int k = l; k <= mid; k++) {
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= n; j++) {
				h[i][j] = min (h[i][j], h[i][k] + h[k][j]);
			}
		}
	}

	for (int k = mid + 1; k <= r; k++) {
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= n; j++) {
				g[i][j] = min (g[i][j], g[i][k] + g[k][j]);
			}
		}
	}

	solve (l, mid, g);
	solve (mid + 1, r, h);
}

int main () {

	freopen ("hopeicanjump.in", "r", stdin);
	freopen ("hopeicanjump.out", "w", stdout);

	fin >> n >> q;

	arr graph (n + 1, vector<long long> (n + 1));

	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			fin >> graph[i][j];
		}
	}

	for (int i = 1; i <= q; i++) {
		int s, t, p;
		fin >> s >> t >> p;
		ques[p].emplace_back(s, t, i);
	}

	solve (1, n, graph);

	for (int i = 1; i <= q; i++) {
		printf ("%lld\n", res[i]);
	}
	
	return 0;
}