#include <bits/stdc++.h>
#pragma GCC optimize("Ofast", "unroll-loops", "omit-frame-pointer", "inline")
#pragma GCC option("arch=native", "tune=native", "no-zero-upper")
#pragma GCC target("avx2")
using namespace std;
template <typename T>
void maxtt(T &t1, T t2) {
  t1 = max(t1, t2);
}
template <typename T>
void mintt(T &t1, T t2) {
  t1 = min(t1, t2);
}
bool debug = 0;
int n, m, k;
int dx[4] = {0, 1, 0, -1}, dy[4] = {1, 0, -1, 0};
string direc = "RDLU";
const long long MOD2 = (long long)1000000007 * (long long)1000000007;
long long ln, lk, lm;
void etp(bool f = 0) {
  puts(f ? "YES" : "NO");
  exit(0);
}
void addmod(int &x, int y, int mod = 1000000007) {
  x += y;
  if (x >= mod) x -= mod;
  if (x < 0) x += mod;
  assert(x >= 0 && x < mod);
}
void et(int x = -1) {
  printf("%d\n", x);
  exit(0);
}
long long fastPow(long long x, long long y, int mod = 1000000007) {
  long long ans = 1;
  while (y > 0) {
    if (y & 1) ans = (x * ans) % mod;
    x = x * x % mod;
    y >>= 1;
  }
  return ans;
}
long long gcd1(long long x, long long y) { return y ? gcd1(y, x % y) : x; }
template <typename C, typename R = C>
struct MaxFlow {
  static const C oo = std::numeric_limits<C>::max();
  struct edge {
    int dst;
    int rev;
    C cap, flowp;
    edge(int src, int dst, int rev, C cap, int flowp)
        : dst(dst), rev(rev), cap(cap), flowp(flowp) {}
  };
  MaxFlow(int n) : adj(n), que(n), level(n), edge_pos(n), flow_id(0) {}
  int add_edge(int src, int dst, C cap, C rcap = 0) {
    adj[src].emplace_back(src, dst, (int)adj[dst].size(), cap, flow_id++);
    if (src == dst) adj[src].back().rev++;
    adj[dst].emplace_back(dst, src, (int)adj[src].size() - 1, rcap, flow_id++);
    return (int)adj[src].size() - 1 - (src == dst);
  }
  inline bool side_of_S(int u) { return level[u] == -1; }
  R max_flow(int source, int sink, vector<C> &flow_e) {
    R flow = 0;
    while (true) {
      int front = 0, back = 0;
      std::fill(level.begin(), level.end(), -1);
      for (level[que[back++] = sink] = 0; front < back && level[source] == -1;
           ++front) {
        int u = que[front];
        for (const edge &e : adj[u])
          if (level[e.dst] == -1 && flow_e[rev(e).flowp] < rev(e).cap)
            level[que[back++] = e.dst] = 1 + level[u];
      }
      if (level[source] == -1) break;
      std::fill(edge_pos.begin(), edge_pos.end(), 0);
      std::function<C(int, C)> find_path = [&](int from, C res) {
        if (from == sink) return res;
        for (int &ept = edge_pos[from]; ept < (int)adj[from].size(); ++ept) {
          edge &e = adj[from][ept];
          if (flow_e[e.flowp] == e.cap || level[e.dst] + 1 != level[from])
            continue;
          C push = find_path(e.dst, std::min(res, e.cap - flow_e[e.flowp]));
          if (push > 0) {
            flow_e[e.flowp] += push;
            flow_e[rev(e).flowp] -= push;
            if (flow_e[e.flowp] == e.cap) ++ept;
            return push;
          }
        }
        return static_cast<C>(0);
      };
      for (C f; (f = find_path(source, oo)) > 0;) flow += f;
    }
    return flow;
  }
  R max_flow2(int source, int sink, vector<C> &flow_e) {
    R flow = 0;
    std::function<C(int, C)> find_path = [&](int from, C res) {
      level[from] = 1;
      if (from == sink) return res;
      for (int &ept = edge_pos[from]; ept < (int)adj[from].size(); ++ept) {
        edge &e = adj[from][ept];
        if (level[e.dst] == 1 || flow_e[e.flowp] == e.cap) continue;
        C push = find_path(e.dst, std::min(res, e.cap - flow_e[e.flowp]));
        if (push > 0) {
          flow_e[e.flowp] += push;
          flow_e[rev(e).flowp] -= push;
          if (flow_e[e.flowp] == e.cap) ++ept;
          return push;
        }
      }
      return static_cast<C>(0);
    };
    for (bool ok = true; ok;) {
      int it = 0;
      std::fill(edge_pos.begin(), edge_pos.end(), 0);
      for (C f;; ++it) {
        std::fill(level.begin(), level.end(), -1);
        f = find_path(source, oo);
        if (f == 0) {
          if (it == 0) ok = false;
          break;
        }
        flow += f;
      }
    }
    return flow;
  }
  int flow_id;

 private:
  std::vector<std::vector<edge>> adj;
  std::vector<int> que;
  std::vector<int> level;
  std::vector<int> edge_pos;
  inline edge &rev(const edge &e) { return adj[e.dst][e.rev]; }
};
vector<pair<pair<int, int>, int>> E;
void relabel() {
  mt19937 urng((int)time(0));
  shuffle(E.begin() + k, E.end(), urng);
  vector<vector<pair<int, int>>> mp(n);
  for (int(i) = 0; (i) < (int)(m); (i)++)
    mp[E[i].first.first].push_back({E[i].first.second, i});
  vector<pair<pair<int, int>, int>> ne = E;
  vector<int> id(n, -1);
  id[0] = 0;
  id[n - 1] = n - 1;
  int sz = 1, esz = k;
  function<void(int)> dfs = [&](int u) {
    for (auto &v : mp[u]) {
      if (v.second >= k) {
        ne[esz++] = E[v.second];
        v.second = -1;
      }
      if (id[v.first] == -1) {
        id[v.first] = sz++;
        dfs(v.first);
      }
    }
  };
  dfs(0);
  for (auto &u : mp)
    for (auto v : u)
      if (v.second >= k) ne[esz++] = E[v.second];
  for (int i = 0; i < n; ++i)
    if (id[i] == -1) id[i] = sz++;
  E = ne;
  for (auto &i : E) {
    i.first.first = id[i.first.first];
    i.first.second = id[i.first.second];
  }
}
struct masks {
  int x, cost;
  vector<int> flow_e;
  bool operator<(const masks &o) const { return cost < o.cost; }
};
void fmain(int tid) {
  int q;
  int I = 25;
  scanf("%d%d%d%d", &n, &m, &k, &q);
  E.resize(m);
  for (int(i) = 0; (i) < (int)(m); (i)++) {
    scanf("%d%d%d", &E[i].first.first, &E[i].first.second, &E[i].second);
    E[i].first.first--;
    E[i].first.second--;
  }
  relabel();
  MaxFlow<int> mf(n);
  for (int(i) = 0; (i) < (int)(m); (i)++)
    mf.add_edge(E[i].first.first, E[i].first.second, i < k ? I : E[i].second);
  vector<int> flow_e(mf.flow_id);
  for (int(i) = 0; (i) < (int)(k); (i)++) flow_e[i << 1] = I;
  vector<int> msk(1 << k, -1);
  msk[0] = mf.max_flow(0, n - 1, flow_e);
  priority_queue<masks> pq;
  pq.push({0, 0, flow_e});
  while (!pq.empty()) {
    int x = pq.top().x;
    flow_e = pq.top().flow_e;
    pq.pop();
    for (int j = 0; j < k; ++j)
      if ((~x >> j & 1) && msk[x | 1 << j] == -1) {
        auto n_flow_e = flow_e;
        n_flow_e[2 * j] = 0;
        msk[x | 1 << j] = msk[x] + mf.max_flow2(0, n - 1, n_flow_e);
        pq.push({x | 1 << j, 0, n_flow_e});
      }
  }
  vector<int> cut(1 << k), bit(1 << k);
  for (int(i) = 0; (i) < (int)(1 << k); (i)++) bit[i] = i & -i;
  int all = (1 << k) - 1;
  for (int(zz) = 1; (zz) <= (int)(q); (zz)++) {
    for (int(i) = 0; (i) < (int)(k); (i)++) scanf("%d", &cut[1 << i]);
    int ans = msk[all];
    for (int(i) = 0; (i) < (int)(1 << k); (i)++) {
      cut[i] = cut[i ^ bit[i]] + cut[bit[i]];
      ans = min(ans, cut[i] + msk[all ^ i]);
    }
    printf("%d\n", ans);
  }
}
int main() {
  int t = 1;
  for (int(i) = 1; (i) <= (int)(t); (i)++) {
    fmain(i);
  }
  return 0;
}
