#include <cstdio>
#include <cctype>

struct IO {
  static const int BUFSIZE = 1 << 20;
  char buf[BUFSIZE], *p1, *p2;
  char pbuf[BUFSIZE], *pp;
  
  IO() : p1(buf), p2(buf), pp(pbuf) {};
  ~IO() { fwrite(pbuf, 1, pp - pbuf, stdout); }
  
  char getchar() {
    if (p1 == p2) {
      p2 = (p1 = buf) + fread(buf, 1, BUFSIZE, stdin);
      if (p1 == p2) return EOF;
    }
    return *p1++;
  }
  
  void putchar(char ch) {
    if (pp - pbuf == BUFSIZE) fwrite(pbuf, 1, BUFSIZE, stdout), pp = pbuf;
    *pp++ = ch;
  }
  
  template <typename T> T read() {
    T res = 0, f = 1;
    char ch = getchar();
    for (; !isdigit(ch); ch = getchar()) if (ch == '-') f = -1;
    for (; isdigit(ch); ch = getchar()) res = (res << 3) + (res << 1) + (ch ^ 48);
    return res * f;
  }
  
  template <typename T> void write(T x, char ed = '\n') {
    if (x < 0) x = -x, putchar('-');
    static int sta[sizeof(T) << 2], top = 0;
    do {
      sta[++top] = x % 10;
      x /= 10;
    } while (x);
    while (top) {
      putchar(sta[top--] ^ 48);
    }
    putchar(ed);
  }
} io;

#include <algorithm>
#include <cstring>
#include <queue>
typedef long long ll;

const int MAXN = 310;

struct EDGE {
  int v;
  ll w;
  int next;
} edge[MAXN * MAXN];

int head[MAXN], edgeNum;
void AddEdge(int u, int v, ll w) {
  edge[++edgeNum] = {v, w, head[u]};
  head[u] = edgeNum;
}

int n, q;
ll dis[MAXN];
bool vis[MAXN];
std::priority_queue<std::pair<ll, int>> pq;

ll Dijkstra(int st, int ed, int del) {
  memset(dis, 0x3f, sizeof dis);
  memset(vis, 0, sizeof vis);
  dis[st] = 0;
  pq.emplace(0, st);
  while (!pq.empty()) {
    int u = pq.top().second;
    pq.pop();
    if (vis[u]) continue;
    vis[u] = 1;
    if (u == del) continue;
    for (int i = head[u]; i; i = edge[i].next) {
      int v = edge[i].v; ll w = edge[i].w;
      if (v == del) continue;
      if (dis[u] + w < dis[v]) {
        dis[v] = dis[u] + w;
        pq.emplace(-dis[v], v);
      }
    }
  }
  return dis[ed];
}

int main() {
#ifdef LOCAL
  freopen("!input.in", "r", stdin);
  freopen("!output.out", "w", stdout);
#else
  freopen("hopeicanjump.in", "r", stdin);
  freopen("hopeicanjump.out", "w", stdout);
#endif
  
  n = io.read<int>(), q = io.read<int>();
  for (int i = 1; i <= n; ++i) {
    for (int j = 1; j <= n; ++j) {
      AddEdge(i, j, io.read<ll>());
    }
  }
  
  while (q--) {
    int s = io.read<int>(), t = io.read<int>(), p = io.read<int>();
    io.write(Dijkstra(s, t, p));
  }
  return 0;
}