#include <bits/stdc++.h>
using namespace std;
const int MAXN = 10 + 60;
const int INF = int(1e9);
int n, m, r;
long long f[MAXN][MAXN][MAXN], a[MAXN][MAXN], dis[MAXN][MAXN];
int main() {
  ({
    n = 0;
    int neg = 0;
    char ch;
    for (ch = getchar(); ch < '0' || ch > '9'; ch = getchar())
      if (ch == '-') neg = 1;
    n = ch - 48;
    for (ch = getchar(); ch >= '0' && ch <= '9'; ch = getchar())
      n = (n << 3) + (n << 1) + ch - 48;
    if (neg) n = -n;
  });
  ({
    m = 0;
    int neg = 0;
    char ch;
    for (ch = getchar(); ch < '0' || ch > '9'; ch = getchar())
      if (ch == '-') neg = 1;
    m = ch - 48;
    for (ch = getchar(); ch >= '0' && ch <= '9'; ch = getchar())
      m = (m << 3) + (m << 1) + ch - 48;
    if (neg) m = -m;
  });
  ({
    r = 0;
    int neg = 0;
    char ch;
    for (ch = getchar(); ch < '0' || ch > '9'; ch = getchar())
      if (ch == '-') neg = 1;
    r = ch - 48;
    for (ch = getchar(); ch >= '0' && ch <= '9'; ch = getchar())
      r = (r << 3) + (r << 1) + ch - 48;
    if (neg) r = -r;
  });
  memset(dis, 0x3f, sizeof(dis));
  for (int kk = 0; kk < m; kk++) {
    for (int i = 1; i <= n; i++)
      for (int j = 1; j <= n; j++)
        ({
          a[i][j] = 0;
          int neg = 0;
          char ch;
          for (ch = getchar(); ch < '0' || ch > '9'; ch = getchar())
            if (ch == '-') neg = 1;
          a[i][j] = ch - 48;
          for (ch = getchar(); ch >= '0' && ch <= '9'; ch = getchar())
            a[i][j] = (a[i][j] << 3) + (a[i][j] << 1) + ch - 48;
          if (neg) a[i][j] = -a[i][j];
        });
    for (int k = 1; k <= n; k++)
      for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++) a[i][j] = min(a[i][j], a[i][k] + a[k][j]);
    for (int i = 1; i <= n; i++)
      for (int j = 1; j <= n; j++) dis[i][j] = min(dis[i][j], a[i][j]);
  }
  memset(f, 0x3f, sizeof(f));
  for (int i = 1; i <= n; i++)
    for (int j = 1; j <= n; j++) f[i][j][0] = dis[i][j];
  for (int kk = 1; kk <= n; kk++)
    for (int k = 1; k <= n; k++)
      for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
          f[i][j][kk] = min(f[i][j][kk], f[i][k][kk - 1] + dis[k][j]);
  int st, fn, change;
  while (r--) {
    ({
      st = 0;
      int neg = 0;
      char ch;
      for (ch = getchar(); ch < '0' || ch > '9'; ch = getchar())
        if (ch == '-') neg = 1;
      st = ch - 48;
      for (ch = getchar(); ch >= '0' && ch <= '9'; ch = getchar())
        st = (st << 3) + (st << 1) + ch - 48;
      if (neg) st = -st;
    });
    ({
      fn = 0;
      int neg = 0;
      char ch;
      for (ch = getchar(); ch < '0' || ch > '9'; ch = getchar())
        if (ch == '-') neg = 1;
      fn = ch - 48;
      for (ch = getchar(); ch >= '0' && ch <= '9'; ch = getchar())
        fn = (fn << 3) + (fn << 1) + ch - 48;
      if (neg) fn = -fn;
    });
    ({
      change = 0;
      int neg = 0;
      char ch;
      for (ch = getchar(); ch < '0' || ch > '9'; ch = getchar())
        if (ch == '-') neg = 1;
      change = ch - 48;
      for (ch = getchar(); ch >= '0' && ch <= '9'; ch = getchar())
        change = (change << 3) + (change << 1) + ch - 48;
      if (neg) change = -change;
    });
    cout << f[st][fn][min(change, n)] << endl;
  }
  return 0;
}
