#include <bits/stdc++.h>
using namespace std;
const int N = 20010, K = 1024, INF = 0x7f7f7f7f;
template <typename T>
void read(T &x) {
  int ch = getchar();
  x = 0;
  bool f = false;
  for (; ch < '0' || ch > '9'; ch = getchar())
    ;
  for (; ch >= '0' && ch <= '9'; ch = getchar()) x = x * 10 + ch - '0';
  if (f) x = -x;
}
template <typename T>
bool chmax(T &a, const T &b) {
  if (a < b) return a = b, 1;
  return 0;
}
template <typename T>
bool chmin(T &a, const T &b) {
  if (a > b) return a = b, 1;
  return 0;
}
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int n, m, k, T, cnt = 1, head[N], to[N], nxt[N], *cap, tmp[K][N], val[K], tt[K],
                pre[N];
void add(int a, int b) {
  to[++cnt] = b;
  nxt[cnt] = head[a];
  head[a] = cnt;
}
int cur[N], dep[N], q[N], f, r;
bool bfs() {
  memset(dep, 0x7f, sizeof dep);
  memcpy(cur, head, sizeof cur);
  f = r = 0;
  q[r++] = 1;
  dep[1] = 0;
  while (f < r) {
    int u = q[f++];
    for (int i = head[u]; i; i = nxt[i])
      if (cap[i] && chmin(dep[to[i]], dep[u] + 1)) q[r++] = to[i];
  }
  return dep[n] < INF;
}
int dfs(int x, int lim) {
  if (!lim || x == n) return lim;
  int flow = 0, f;
  for (int &i = cur[x]; i; i = nxt[i])
    if (dep[to[i]] == dep[x] + 1 && (f = dfs(to[i], min(cap[i], lim - flow)))) {
      flow += f;
      cap[i] -= f;
      cap[i ^ 1] += f;
      if (flow == lim) break;
    }
  return flow;
}
int Bfs() {
  memset(dep, 0x7f, sizeof dep);
  f = r = 0;
  q[r++] = 1;
  dep[1] = 0;
  while (f < r) {
    int u = q[f++];
    for (int i = head[u]; i; i = nxt[i])
      if (cap[i] && chmin(dep[to[i]], dep[u] + 1)) {
        q[r++] = to[i];
        pre[to[i]] = i;
        if (to[i] == n) {
          f = r = 0;
          break;
        }
      }
  }
  if (dep[n] == INF) return 0;
  int flow = INF;
  for (int now = n; now != 1; now = to[pre[now] ^ 1])
    chmin(flow, cap[pre[now]]);
  for (int now = n; now != 1; now = to[pre[now] ^ 1]) {
    cap[pre[now]] -= flow;
    cap[pre[now] ^ 1] += flow;
  }
  return flow;
}
int main() {
  read(n);
  read(m);
  read(k);
  read(T);
  int lim = (1 << k) - 1;
  for (int i = 0, u, v; i < m; ++i) {
    read(u);
    read(v);
    add(u, v);
    add(v, u);
    tmp[lim][cnt] = 0;
    read(tmp[lim][cnt ^ 1]);
  }
  cap = tmp[lim];
  while (bfs()) val[lim] += dfs(1, INF);
  for (int S = lim - 1; ~S; --S) {
    int mv = -1, mp, f;
    for (int i = 0; i < k; ++i)
      if (!(S >> i & 1)) {
        int now = S | (1 << i);
        if (chmax(mv, val[now]) || (mv == val[now] && (rng() & 1))) mp = i;
      }
    cap = tmp[S];
    memcpy(cap, tmp[S | (1 << mp)], sizeof tmp[S]);
    cap[mp + 1 << 1] = 25;
    val[S] = val[S | (1 << mp)];
    while (f = Bfs()) val[S] += f;
  }
  while (T--) {
    for (int i = 0; i < k; ++i) read(tt[1 << i]);
    int res = INF;
    for (int S = 0; S <= lim; ++S) {
      tt[S] = tt[S ^ (S & -S)] + tt[S & -S];
      chmin(res, tt[S] + val[S]);
    }
    printf("%d\n", res);
  }
}
