#include <bits/stdc++.h>
using namespace std;
inline int read() {
  int x = 0, f = 1;
  char ch = getchar();
  while (!isdigit(ch)) {
    if (ch == '-') f = -1;
    ch = getchar();
  }
  while (isdigit(ch)) {
    x = (x << 1) + (x << 3) + ch - '0';
    ch = getchar();
  }
  return x * f;
}
const int N = 10005;
int n, m, k, Q, x[15], y[15], head[N], tab[15][N * 2],
    tot = 1, dis[N], q[N], cur[N], co[N], f[N], id[15], vis[N], visT;
struct edge {
  int to, next, f;
} e[N * 2];
inline void add(int x, int y, int v) {
  e[++tot] = (edge){y, head[x], v};
  head[x] = tot;
  e[++tot] = (edge){x, head[y], 0};
  head[y] = tot;
}
inline bool bfs() {
  int h = 0, t = 1;
  vis[1] = ++visT;
  q[1] = 1;
  dis[1] = 0;
  cur[1] = head[1];
  while (h != t) {
    int x = q[++h];
    for (int i = head[x]; i; i = e[i].next)
      if (vis[e[i].to] != visT && e[i].f) {
        dis[e[i].to] = dis[x] + 1;
        vis[e[i].to] = visT;
        cur[e[i].to] = head[e[i].to];
        if (e[i].to == n) return 1;
        q[++t] = e[i].to;
      }
  }
  return 0;
}
inline int bfss() {
  int h = 0, t = 1;
  vis[1] = ++visT;
  q[1] = 1;
  cur[1] = 0;
  while (h != t) {
    int x = q[++h];
    for (int i = head[x]; i; i = e[i].next)
      if (vis[e[i].to] != visT && e[i].f) {
        vis[e[i].to] = visT;
        cur[e[i].to] = i;
        if (e[i].to == n) {
          int mn = 1 << 30;
          for (int j = cur[n]; j; j = cur[e[j ^ 1].to]) mn = min(mn, e[j].f);
          for (int j = cur[n]; j; j = cur[e[j ^ 1].to]) {
            e[j].f -= mn;
            e[j ^ 1].f += mn;
          }
          return mn;
        }
        q[++t] = e[i].to;
      }
  }
  return 0;
}
inline int dfs(int x, int flow) {
  if (x == n) return flow;
  int k, rest = flow;
  for (int &i = cur[x]; i && rest; i = e[i].next)
    if (dis[e[i].to] == dis[x] + 1 && vis[e[i].to] == visT && e[i].f) {
      k = dfs(e[i].to, min(e[i].f, flow));
      e[i].f -= k;
      e[i ^ 1].f += k;
      rest -= k;
      if (!rest) break;
    }
  if (rest) dis[x] = -1;
  return flow - rest;
}
int times = 0, tmpclk = 0;
inline void dfs(int d, int S, int v) {
  if (d == k + 1) {
    co[S >> 1] = v;
    return;
  }
  int p = id[d];
  dfs(d + 1, S | (1 << p), v);
  for (int i = (int)(1); i <= (int)(tot); i++) tab[d][i] = e[i].f;
  int t1 = head[x[p]], t2 = head[y[p]];
  add(x[p], y[p], 25);
  for (int val; val = bfss(); v += val)
    ;
  dfs(d + 1, S, v);
  head[x[p]] = t1;
  head[y[p]] = t2;
  tot -= 2;
  for (int i = (int)(1); i <= (int)(tot); i++) e[i].f = tab[d][i];
}
int main() {
  srand(time(NULL));
  n = read();
  m = read();
  k = read();
  Q = read();
  for (int i = (int)(1); i <= (int)(k); i++) scanf("%d%d%*d", &x[i], &y[i]);
  for (int i = (int)(k + 1); i <= (int)(m); i++) {
    int x = read(), y = read(), v = read();
    add(x, y, v);
  }
  int inif = 0;
  for (; bfs(); inif += dfs(1, 1 << 20))
    ;
  tmpclk = clock();
  for (int i = (int)(1); i <= (int)(k); i++) id[i] = i;
  random_shuffle(id + 1, id + k + 1);
  dfs(1, 0, inif);
  while (Q--) {
    for (int i = (int)(0); i <= (int)(k - 1); i++) f[1 << i] = read();
    for (int i = (int)(1); i <= (int)((1 << k) - 1); i++)
      f[i] = f[i - (i & (-i))] + f[i & (-i)];
    int ans = 1 << 30;
    for (int i = (int)(0); i <= (int)((1 << k) - 1); i++)
      ans = min(ans, co[i] + f[i]);
    printf("%d\n", ans);
  }
  return 0;
}
