#include <bits/stdc++.h>
using namespace std;
const int maxm = 20010, maxn = 10010, maxk = 1110;
const int inf = 1e7;
int to1[maxm], begin1[maxn], next1[maxm], w[maxm][maxk], cur[maxn], e = 1,
                                                                    W[maxm];
int d[maxn], q[maxn], g[maxk], ans[maxk], vis[maxn], pre[maxn], lg[maxn],
    t[maxk];
int tot, n;
struct node {
  int x, f;
} Q[maxn];
void read(int &x) {
  x = 0;
  char c = getchar();
  while (!('0' <= c && c <= '9')) c = getchar();
  while ('0' <= c && c <= '9') {
    x = (x << 3) + (x << 1) + c - '0';
    c = getchar();
  }
}
void add(int x, int y, int z) {
  to1[++e] = y;
  next1[e] = begin1[x];
  begin1[x] = e;
  w[e][0] = z;
}
int min(int x, int y) { return x < y ? x : y; }
int bfs(int x, int y) {
  int r = 0, l = 1, i;
  for (i = 1; i <= y; i++) d[i] = 0;
  q[0] = x;
  d[x] = 1;
  while (r < l) {
    int xx = q[r];
    r++;
    for (i = begin1[xx]; i; i = next1[i])
      if (!d[to1[i]] && w[i][0]) {
        d[to1[i]] = d[xx] + 1;
        q[l] = to1[i];
        l++;
      }
  }
  return d[y];
}
int dfs(int x, int y, int sum) {
  int i;
  if (x == y) return sum;
  int flow = 0;
  for (int &i = cur[x]; i; i = next1[i]) {
    if (d[to1[i]] == d[x] + 1 && w[i][0]) {
      int h = dfs(to1[i], y, min(sum, w[i][0]));
      w[i][0] -= h;
      w[i ^ 1][0] += h;
      flow += h;
      sum -= h;
      if (!sum) break;
    }
  }
  if (flow == 0) d[x] = -1;
  return flow;
}
int Bfs(int x, int y) {
  int r = 0, l = 1, flag = 0, i;
  Q[r].x = x;
  Q[r].f = 25;
  vis[x] = tot;
  while (r < l) {
    node xx = Q[r];
    r++;
    for (i = begin1[xx.x]; i; i = next1[i]) {
      if (W[i] && vis[to1[i]] != tot) {
        vis[to1[i]] = tot;
        pre[to1[i]] = i;
        Q[l].x = to1[i];
        Q[l].f = min(xx.f, W[i]);
        if (to1[i] == n) {
          flag = 1;
          break;
        }
        l++;
      }
    }
    if (flag) break;
  }
  int ans = 0;
  if (flag) {
    ans = Q[l].f;
    int now = n;
    while (now != 1) {
      W[pre[now]] -= ans;
      W[pre[now] ^ 1] += ans;
      now = to1[pre[now] ^ 1];
    }
  }
  return ans;
}
int main() {
  int i, j, m, k, q, x, y, z;
  read(n);
  read(m);
  read(k);
  read(q);
  for (i = 1; i <= m; i++) {
    read(x);
    read(y);
    read(z);
    add(x, y, z);
    add(y, x, 0);
  }
  while (bfs(1, n)) {
    for (i = 1; i <= n; i++) cur[i] = begin1[i];
    int h = dfs(1, n, inf);
    while (h) {
      ans[0] += h;
      h = dfs(1, n, inf);
    }
  }
  lg[1] = 1;
  for (i = 2; i < (1 << k); i <<= 1) lg[i] = lg[i >> 1] + 1;
  for (i = 1; i < (1 << k); i++) {
    int p = i - (i & (-i));
    for (j = 2; j <= e; j++) w[j][i] = w[j][p];
    ans[i] = ans[p];
    w[lg[(i & (-i))] << 1][i] = 25;
    ++tot;
    for (j = 1; j <= e; j++) W[j] = w[j][i];
    int h = Bfs(1, n);
    while (h) {
      ans[i] += h;
      ++tot;
      h = Bfs(1, n);
    }
    for (j = 1; j <= e; j++) w[j][i] = W[j];
  }
  while (q--) {
    int sum = ans[0];
    g[0] = 0;
    for (i = 1; i <= k; i++) {
      read(t[i]);
      sum += t[i];
      g[0] += t[i];
    }
    for (i = 1; i < (1 << k); i++) {
      int p = i - (i & (-i)), &h = g[i];
      h = g[p];
      h -= t[lg[i & (-i)]];
      sum = min(sum, h + ans[i]);
    }
    printf("%d\n", sum);
  }
}
