#include <bits/stdc++.h>
using namespace std;
inline void read(int &x) {
  x = 0;
  char c = getchar();
  int f = 1;
  while (!isdigit(c)) {
    if (c == '-') f = -1;
    c = getchar();
  }
  while (isdigit(c)) {
    x = x * 10 + c - '0';
    c = getchar();
  }
  x *= f;
}
inline unsigned int R() {
  static unsigned int seed = 416;
  return seed ^= seed >> 5, seed ^= seed << 17, seed ^= seed >> 13;
}
const int N = 20220, M = 240030, inf = 0x3f3f3f3f;
int n, m, k, A[N], B[N], C[N], ans[1 << 13 | 3], S, T, head[N], cur[N], nxt[M],
    cap[M], to[M], edgenum = 1;
void addedge(int u, int v, int c) {
  to[++edgenum] = v;
  cap[edgenum] = c;
  nxt[edgenum] = head[u];
  head[u] = edgenum;
}
void add(int u, int v, int c) {
  addedge(u, v, c);
  addedge(v, u, 0);
}
int dis[N], q[N];
pair<int *, int> rec[10000000];
int top;
inline bool bfs() {
  memset(dis, inf, 4 * (T + 2));
  int f = 0, r = 1;
  q[f] = T;
  dis[T] = 0;
  while (f != r) {
    int u = q[f++];
    for (register int i = head[u]; i; i = nxt[i])
      if (cap[i ^ 1] && dis[to[i]] == inf) {
        q[r++] = to[i];
        dis[to[i]] = dis[u] + 1;
        if (to[i] == S) return 1;
      }
  }
  return dis[S] < inf;
}
template <class T>
inline void umin(T &x, T y) {
  x = x < y ? x : y;
}
int dfs(int u, int flow) {
  if (u == T || !flow) return flow;
  int res = 0;
  for (register int &i = cur[u]; i; i = nxt[i])
    if (cap[i] && dis[u] == dis[to[i]] + 1) {
      int tmp = dfs(to[i], min(flow, cap[i]));
      res += tmp;
      flow -= tmp;
      rec[++top] = make_pair(cap + i, cap[i]);
      rec[++top] = make_pair(cap + (i ^ 1), cap[i ^ 1]);
      cap[i] -= tmp;
      cap[i ^ 1] += tmp;
      if (!flow) break;
    }
  return res;
}
inline int dinic() {
  int res = 0;
  while (bfs()) {
    memcpy(cur, head, 4 * (T + 2));
    res += dfs(S, inf);
  }
  return res;
}
static int w[N];
void dfs2(int dep, int S, int cur) {
  ans[S] = cur;
  for (register int i = (dep); i <= (k); i++) {
    int lst = top;
    add(A[i], B[i], 25);
    int tmp = cur + dinic();
    dfs2(i + 1, S | 1 << i - 1, tmp);
    while (top > lst) {
      *rec[top].first = rec[top].second;
      top--;
    }
    edgenum -= 2;
    head[A[i]] = nxt[head[A[i]]];
    head[B[i]] = nxt[head[B[i]]];
  }
}
void dfs3(int dep, int S, int &res, int cur) {
  if (dep > k) {
    umin(res, cur + ans[(1 << k) - 1 - S]);
    return;
  }
  dfs3(dep + 1, S, res, cur);
  dfs3(dep + 1, S | 1 << dep - 1, res, cur + w[dep]);
}
int main() {
  read(n);
  read(m);
  read(k);
  int q;
  read(q);
  S = 1;
  T = n;
  for (register int i = (1); i <= (m); i++) {
    read(A[i]), read(B[i]), read(C[i]);
    if (i > k) add(A[i], B[i], C[i]);
  }
  int tmp = dinic();
  top = 0;
  dfs2(1, 0, tmp);
  while (q--) {
    for (register int i = (1); i <= (k); i++) read(w[i]);
    int res = 2e9;
    dfs3(1, 0, res, 0);
    printf("%d\n", res);
  }
  return 0;
}
