#include <bits/stdc++.h>
using namespace std;
int read() {
  int s = 0;
  char ch = getchar();
  while (ch < '0' || ch > '9') ch = getchar();
  while (ch >= '0' && ch <= '9') {
    s = (s << 1) + (s << 3) + (ch ^ 48);
    ch = getchar();
  }
  return s;
}
int n, m, w, qq, ans[1 << 10];
int fi[10004], cur[10004], ne[10004 << 1], to[10004 << 1],
    l[1 << 10][10004 << 1], num = 1;
void add(int x, int y, int z) {
  ne[++num] = fi[x];
  fi[x] = num;
  to[num] = y;
  for (int i = 0; i < (1 << w); i++) l[i][num] = z;
  ne[++num] = fi[y];
  fi[y] = num;
  to[num] = x;
}
int dis[10004];
bool bfs() {
  memset(dis, 0x3f, sizeof(dis));
  queue<int> q;
  dis[1] = 0;
  q.push(1);
  int x;
  while (!q.empty()) {
    x = q.front();
    q.pop();
    for (int i = fi[x]; i; i = ne[i])
      if (dis[to[i]] > dis[x] + 1 && l[0][i]) {
        dis[to[i]] = dis[x] + 1;
        q.push(to[i]);
      }
  }
  return dis[n] < 0x3f3f3f3f;
}
bool fla;
int dfs(int k, int flow) {
  if (k == n) {
    fla = true;
    return flow;
  }
  int us = 0, rlow;
  for (int& i = cur[k]; i; i = ne[i])
    if (l[0][i] && dis[to[i]] == dis[k] + 1)
      if (rlow = dfs(to[i], min(flow - us, l[0][i]))) {
        l[0][i] -= rlow;
        l[0][i ^ 1] += rlow;
        us += rlow;
        if (us == flow) break;
      }
  return us;
}
void dinic() {
  while (bfs()) {
    fla = true;
    for (int i = 1; i <= n; i++) cur[i] = fi[i];
    while (fla) {
      fla = false;
      ans[0] += dfs(1, 0x3f3f3f3f);
    }
  }
}
bool vis[10004];
int zzz;
int ddfs(int k, int flow) {
  if (k == n) return flow;
  int rlow;
  vis[k] = 1;
  for (int i = fi[k]; i; i = ne[i])
    if (l[zzz][i] && !vis[to[i]])
      if (rlow = ddfs(to[i], min(flow, l[zzz][i]))) {
        l[zzz][i] -= rlow;
        l[zzz][i ^ 1] += rlow;
        return rlow;
      }
  return 0;
}
int ll[1 << 10], s[1 << 10];
int main() {
  n = read();
  m = read();
  w = read();
  qq = read();
  int x, y, z;
  for (int i = 1; i <= m; i++) {
    x = read();
    y = read();
    z = read();
    add(x, y, z);
  }
  dinic();
  y = 1;
  z = 1;
  srand(time(0));
  for (int i = 1; i < (1 << w); i++) {
    if (i >= (1 << z)) z++, y <<= 1;
    x = rand() & 1 ? y : (i & (-i));
    for (int j = 2; j <= num; j++)
      l[i][j] = j <= 20 && (1 << ((j >> 1) - 1)) == x && (j & 1) == 0
                    ? 25
                    : l[i ^ x][j];
    ans[i] = ans[i ^ x];
    memset(vis, 0, sizeof(vis));
    zzz = i;
    x = ddfs(1, 0x3f3f3f3f);
    while (x) {
      ans[i] += x;
      memset(vis, 0, sizeof(vis));
      x = ddfs(1, 0x3f3f3f3f);
    }
  }
  while (qq--) {
    for (int i = 1; i <= w; i++) ll[1 << (i - 1)] = read();
    for (int i = 1; i < (1 << w); i++)
      s[i] = s[i ^ (i & (-i))] + ll[(i & (-i))];
    x = 0x3f3f3f3f;
    for (int i = 0; i < (1 << w); i++)
      x = min(x, ans[i] + s[((1 << w) - 1) ^ i]);
    printf("%d\n", x);
  }
  return 0;
}
