#include <bits/stdc++.h>
int min(int a, int b) { return a < b ? a : b; }
int ij[10000], cc[10000 * 2], m;
int *oh[10000], oo[10000], n;
void link(int i, int h) {
  int o = oo[i]++;
  if (o >= 2 && (o & o - 1) == 0)
    oh[i] = (int *)realloc(oh[i], o * 2 * sizeof *oh[i]);
  oh[i][o] = h;
}
int dd[10000];
int bfs(int s, int t) {
  static int qu[10000];
  int i, head, cnt;
  for (i = 0; i < n; i++) dd[i] = n;
  head = cnt = 0;
  dd[s] = 0, qu[head + cnt++] = s;
  while (cnt) {
    int d, o;
    i = qu[cnt--, head++], d = dd[i] + 1;
    for (o = 0; o < oo[i]; o++) {
      int h_ = oh[i][o];
      if (cc[h_]) {
        int h = h_ >> 1, j = i ^ ij[h];
        if (dd[j] > d) {
          dd[j] = d;
          if (j == t) return 1;
          qu[head + cnt++] = j;
        }
      }
    }
  }
  return 0;
}
int dfs(int i, int t, int c) {
  int d, o;
  if (i == t) return c;
  d = dd[i] + 1;
  for (o = 0; o < oo[i]; o++) {
    int h_ = oh[i][o];
    if (cc[h_]) {
      int h = h_ >> 1, j = i ^ ij[h];
      if (dd[j] == d) {
        int f = dfs(j, t, min(c, cc[h_]));
        if (f) {
          cc[h_] -= f, cc[h_ ^ 1] += f;
          return f;
        }
      }
    }
  }
  dd[i] = n;
  return 0;
}
int dinic(int s, int t) {
  int sum = 0;
  while (bfs(s, t)) {
    int f;
    while ((f = dfs(s, t, 26))) sum += f;
  }
  return sum;
}
int ccc[10][10000 * 2];
int cut[1 << 10], k;
void solve(int b, int h_, int s) {
  int h;
  s += dinic(0, n - 1);
  cut[b] = s;
  if (h_ < k) {
    memcpy(ccc[h_], cc, m * 2 * sizeof *cc);
    for (h = h_; h < k; h++) {
      cc[h << 1] = 26;
      solve(b | 1 << h, h + 1, s);
      memcpy(cc, ccc[h_], m * 2 * sizeof *ccc[h_]);
    }
  }
}
int main() {
  static int ww_[10];
  int q, h, i, j;
  scanf("%d%d%d%d", &n, &m, &k, &q);
  for (i = 0; i < n; i++) oh[i] = (int *)malloc(2 * sizeof *oh[i]);
  for (h = 0; h < m; h++) {
    int c;
    scanf("%d%d%d", &i, &j, &c), i--, j--;
    ij[h] = i ^ j, cc[h << 1] = c;
    link(i, h << 1), link(j, h << 1 | 1);
  }
  solve(0, 0, 0);
  while (q--) {
    int b, w, ans;
    w = 0;
    for (h = 0; h < k; h++) {
      scanf("%d", &ww_[h]);
      w += ww_[h];
    }
    ans = cut[0] + w;
    for (b = 1; b < 1 << k; b++) {
      for (h = 0; (b & 1 << h) == 0; h++) w += ww_[h];
      w -= ww_[h];
      ans = min(ans, cut[b] + w);
    }
    printf("%d\n", ans);
  }
  return 0;
}
