#include <bits/stdc++.h>
using namespace std;
const int maxn = 10000;
const int maxm = 20000;
const int maxk = 10;
const int inf = 25;
int tot_edge, sz;
int head[maxn];
int nxt[maxm];
int to[maxm];
int cap[maxm];
int flow[maxk + 1][maxm];
int qu[maxn];
int prv[maxn];
int when[maxn];
int pass_flow[maxn];
int last_time;
int level[maxn], edge_pos[maxn];
int read() {
  int xx = 0, ff = 1;
  char ch = getchar();
  while (ch > '9' || ch < '0') {
    if (ch == '-') ff = -1;
    ch = getchar();
  }
  while (ch >= '0' && ch <= '9') {
    xx = (xx << 3) + (xx << 1) + ch - '0';
    ch = getchar();
  }
  return xx * ff;
}
void add_edge(int u, int v, int w) {
  nxt[tot_edge] = head[u];
  head[u] = tot_edge;
  to[tot_edge] = v;
  cap[tot_edge] = w;
  tot_edge++;
}
bool bfs(int s, int t, int *flow) {
  sz = 0;
  qu[sz++] = t;
  int pnt = 0;
  memset(level, -1, sizeof(level));
  level[t] = 0;
  while (pnt < sz && level[s] == -1) {
    int u = qu[pnt++];
    for (int e = head[u]; e >= 0; e = nxt[e]) {
      int v = to[e];
      if (level[v] == -1 && flow[e ^ 1] < cap[e ^ 1]) {
        level[v] = level[u] + 1;
        qu[sz++] = v;
      }
    }
  }
  return level[s] != -1;
}
int dinic(int s, int t, int *flow) {
  int ret = 0;
  while (bfs(s, t, flow)) {
    copy(head, head + maxn, edge_pos);
    function<int(int, int)> find_path = [&](int u, int res) {
      if (u == t) return res;
      for (int &e = edge_pos[u]; e >= 0; e = nxt[e]) {
        int v = to[e];
        if (flow[e] == cap[e] || level[u] - 1 != level[v]) continue;
        int push = find_path(v, min(res, cap[e] - flow[e]));
        if (push > 0) {
          flow[e] += push;
          flow[e ^ 1] -= push;
          if (flow[e] == cap[e]) e = nxt[e];
          return push;
        }
      }
      return 0;
    };
    for (int f; (f = find_path(s, 1e9)) > 0;) ret += f;
  }
  return ret;
}
int augment(int s, int t, int *flow) {
  last_time++;
  sz = 0;
  qu[sz++] = s;
  when[s] = last_time;
  int pnt = 0;
  pass_flow[s] = inf;
  pass_flow[t] = 0;
  while (pnt < sz && when[t] != last_time) {
    int u = qu[pnt++];
    assert(pass_flow[u] > 0);
    for (int e = head[u]; e >= 0; e = nxt[e]) {
      int v = to[e];
      if (when[v] != last_time && flow[e] < cap[e]) {
        pass_flow[v] = min(pass_flow[u], cap[e] - flow[e]);
        prv[v] = e;
        when[v] = last_time;
        qu[sz++] = v;
        if (v == t) break;
      }
    }
  }
  int f = pass_flow[t];
  if (f == 0) return f;
  do {
    int e = prv[t];
    flow[e] += f;
    flow[e ^ 1] -= f;
    assert(to[e] == t);
    t = to[e ^ 1];
  } while (t != s);
  return f;
}
int max_flow(int s, int t, int *flow) {
  int res = 0, cur = 0;
  do {
    cur = augment(s, t, flow);
    res += cur;
  } while (cur);
  return res;
}
int n, m, k, q;
int masked[1 << maxk];
void go(int n, int m, int mask, int pointer) {
  for (int i = 0; (mask >> i & 1) == 0 && i < k; ++i) {
    int n_mask = mask | (1 << i);
    copy(flow[pointer], flow[pointer] + m, flow[pointer + 1]);
    cap[2 * i] = inf;
    masked[n_mask] = masked[mask] + max_flow(0, n - 1, flow[pointer + 1]);
    go(n, m, n_mask, pointer + 1);
    cap[2 * i] = 0;
  }
}
int wei[maxk];
int suma[1 << maxk];
int eptr;
struct info {
  int u, v, w;
} edges[maxm];
vector<int> adj[maxn];
void relabel(int n, int m) {
  sz = 0;
  qu[sz++] = 0;
  int pnt = 0;
  memset(level, -1, sizeof(level));
  level[0] = 0;
  level[n - 1] = n - 1;
  while (pnt < sz) {
    int u = qu[pnt++];
    for (auto v : adj[u]) {
      if (level[v] == -1) {
        level[v] = sz;
        qu[sz++] = v;
      }
    }
  }
  for (int i = 0; i < n; ++i)
    if (level[i] == -1) level[i] = sz++;
  for (int i = 0; i < m; ++i) {
    edges[i].u = level[edges[i].u];
    edges[i].v = level[edges[i].v];
  }
}
int main() {
  memset(head, -1, sizeof head);
  n = read();
  m = read();
  k = read();
  q = read();
  for (int i = 0; i < m; ++i) {
    int u, v, w;
    u = read();
    v = read();
    w = read();
    u--;
    v--;
    edges[i] = {u, v, w};
    adj[u].push_back(v);
  }
  relabel(n, m);
  for (int i = 0; i < m; ++i) {
    add_edge(edges[i].u, edges[i].v, edges[i].w);
    add_edge(edges[i].v, edges[i].u, 0);
  }
  masked[0] = dinic(0, n - 1, flow[0]);
  go(n, 2 * m, 0, 0);
  int top = (1 << k) - 1;
  for (int i = 0; i < q; ++i) {
    for (int j = 0; j < k; ++j) wei[j] = read();
    int answer = masked[top];
    for (int j = 1; j < (1 << k); j++) {
      int x = __builtin_ctz(j);
      suma[j] = suma[j ^ (1 << x)] + wei[x];
      answer = min(answer, masked[top ^ j] + suma[j]);
    }
    printf("%d\n", answer);
  }
  return 0;
}
