#include <bits/stdc++.h>
using namespace std;
const int N = 1e4 + 1, M = 2e4 + 2, INF = 25, L = 1025, O = 15;
int f[N], ne[M], t[M], w[L][M], b = 1, v[N], d[N], n, k, a[L], g[O], s[L], l[L],
                                T, S, c[N], e;
bool r[N];
char bu[1 << 24];
inline char get() {
  if (S == T) {
    S = 0;
    T = fread(bu, 1, 1 << 24, stdin);
    if (S == T) return EOF;
  }
  return bu[S++];
}
int read() {
  int x = 0;
  char c;
  do c = get();
  while (c < '0' || '9' < c);
  while ('0' <= c && c <= '9') {
    x = x * 10 + (c - 48);
    c = get();
  }
  return x;
}
void add(int x, int y, int z) {
  ne[++b] = f[x];
  f[x] = b;
  t[b] = y;
  w[0][b] = z;
}
bool bfs() {
  queue<int> q;
  q.push(1);
  memset(d, 0, sizeof(d));
  d[1] = 1;
  while (!q.empty()) {
    v[q.front()] = f[q.front()];
    for (int i = f[q.front()]; i; i = ne[i]) {
      if (w[0][i] && !d[t[i]]) {
        d[t[i]] = d[q.front()] + 1;
        q.push(t[i]);
      }
    }
    q.pop();
  }
  return d[n] > 0;
}
int dfs(int x, int m) {
  if (x == n) return m;
  int useflow = 0;
  for (int i = v[x]; i && m; i = ne[i]) {
    v[x] = i;
    if (d[t[i]] == d[x] + 1 && w[0][i]) {
      int f = dfs(t[i], min(w[0][i], m));
      if (!f) d[t[i]] = -1;
      w[0][i] -= f;
      w[0][i ^ 1] += f;
      m -= f, useflow += f;
    }
  }
  return useflow;
}
int dnc() {
  int a = 0;
  while (bfs()) {
    int f;
    while (f = dfs(1, INF)) a += f;
  }
  return a;
}
int lb(int x) { return -x & x; }
int fa[N], id[N];
std::queue<int> Q;
int rbfs(int st, int u) {
  memset(d, 0, sizeof(d));
  d[st] = 1;
  Q.push(st);
  while (!Q.empty()) {
    int now = Q.front();
    Q.pop();
    for (int i = f[now]; i; i = ne[i]) {
      int v = t[i];
      if (w[u][i] && !d[v]) {
        d[v] = d[now] + 1;
        Q.push(v);
        fa[v] = now, id[v] = i;
      }
      if (d[n]) break;
    }
  }
  if (!d[n]) return 0;
  int Min = INF, now = n;
  while (now != st) Min = min(Min, w[u][id[now]]), now = fa[now];
  now = n;
  while (now != st)
    w[u][id[now]] -= Min, w[u][id[now] ^ 1] += Min, now = fa[now];
  return Min;
}
int main() {
  int m, q, x, y, z, an, t, tat;
  n = read(), m = read(), k = read(), q = read();
  for (int i = 1; i <= m; i++) {
    x = read(), y = read(), z = read();
    add(x, y, z), add(y, x, 0);
  }
  a[0] = dnc();
  l[1] = 1;
  for (int i = 2; i < (1 << k); i <<= 1) l[i] = l[i >> 1] + 1;
  for (int i = 1; i < (1 << k); i++) {
    for (int j = 2; j <= b; j++) w[i][j] = w[i ^ lb(i)][j];
    w[i][l[lb(i)] << 1] = INF;
    a[i] = a[i ^ lb(i)];
    while (z = rbfs(1, i)) {
      a[i] += z;
    }
  }
  for (int i = 1; i <= q; i++) {
    an = 1e9;
    for (int j = 1; j <= k; j++) g[j] = read();
    for (int j = 1, t = 1 << k; j < t; j++) s[j] = s[j ^ lb(j)] + g[l[lb(j)]];
    for (int j = 0, t = 1 << k; j < t; j++) {
      tat = s[j] + a[(t - 1) ^ j];
      if (tat < an) an = tat;
    }
    printf("%d\n", an);
  }
}
