#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <memory.h>
#include <math.h>
#include <assert.h>
#include <queue>
#include <map>
#include <set>
#include <string>
#include <algorithm>
#include <iostream>
#include <functional>
#include <unordered_map>
#include <unordered_set>
#include <list>
#include <bitset>
using namespace std;
typedef long long ll;
#define Fi first
#define Se second
#define pb(x) push_back(x)
#define szz(x) ((int)(x).size())
#define rep(i, n) for(int i=0;i<n;i++)
#define all(x) (x).begin(), (x).end()
typedef tuple<int, int, int> t3;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef long double ldouble;
typedef pair<ll, int> pli;
int N, M, T, L;
t3 edgen[4040];
int edgec[2020][2020];
vector <pii> IE[2020];
vector <int> nume[2020];
vector <int> numl[2020], numr[2020];
vector <pii> E[20020];
int cs;
void addedge(int x, int y, int c) {
E[x].pb(pii(c, y));
}
ll dis[4040][4040], dtemp[12020];
int X[100010];
pii query[100010];
typedef pair<ll, pii> plp;
void updplp(plp &a, plp &b) {
if(a.Fi > b.Fi) a = b;
else if(a.Fi == b.Fi && a.Se > b.Se) a = b;
}
vector <ll> Val[2020][2020];
vector <pii> Idx[2020][2020];
struct node {
node(){}
node(int s, int e) {
V = Val[s][e];
idx = Idx[s][e];
}
vector <ll> V;
vector <pii> idx;
ll Get() {
ll res = 1e18;
for(ll e : V) res = min(res, e);
return res;
}
};
node merge(const node &lhs, const node &rhs) {
node res;
int n = szz(lhs.V), m = szz(rhs.V);
map <pii, ll> Mx;
rep(i, n) rep(j, m) if(lhs.idx[i].Se != rhs.idx[j].Fi) {
pii t = pii(lhs.idx[i].Fi, rhs.idx[j].Se);
ll val = lhs.V[i] + rhs.V[j];
if(Mx.find(t) == Mx.end() || Mx[t] > val) Mx[t] = val;
}
for(auto e : Mx) {
res.V.pb(e.Se);
res.idx.pb(e.Fi);
}
return res;
}
node Tr[1<<18];
void Init(int rt, int l, int r) {
if(l == r) {
Tr[rt] = node(X[l], X[l+1]);
return;
}
int m = (l + r) >> 1;
Init(rt<<1, l, m);
Init(rt<<1|1, m+1, r);
Tr[rt] = merge(Tr[rt<<1], Tr[rt<<1|1]);
}
void update(int rt, int l, int r, int x) {
if(l == r) {
Tr[rt] = node(X[l], X[l+1]);
return;
}
int m = (l + r) >> 1;
if(x <= m) update(rt<<1, l, m, x);
else update(rt<<1|1, m+1, r, x);
Tr[rt] = merge(Tr[rt<<1], Tr[rt<<1|1]);
}
int main() {
memset(edgec, -1, sizeof edgec);
scanf("%d%d%d%d", &N, &M, &T, &L);
rep(i, M) {
int x, y, z;
scanf("%d%d%d", &x, &y, &z);
edgen[i<<1] = t3(x, y, z);
edgec[x][y] = i<<1;
edgen[i<<1|1] = t3(y, x, z);
edgec[y][x] = i<<1|1;
nume[x].pb(cs++);
nume[y].pb(cs++);
IE[x].pb(pii(z, y));
IE[y].pb(pii(z, x));
}
for(int i=1;i<=N;i++) {
int l = szz(IE[i]);
numl[i].resize(l);
numr[i].resize(l);
rep(j, l) numl[i][j] = cs++;
rep(j, l) numr[i][j] = cs++;
for(int j=1;j<l;j++) {
int x = numl[i][j-1], y = numl[i][j];
addedge(y, x, 0);
x = numr[i][j-1], y = numr[i][j];
addedge(x, y, 0);
}
rep(j, l) {
addedge(numl[i][j], nume[i][j], 0);
addedge(numr[i][j], nume[i][j], 0);
}
rep(j, l) {
int x = nume[i][j] ^ 1, len = get<2>(edgen[x]);
if(j) addedge(x, numl[i][j-1], len);
if(j < l-1) addedge(x, numr[i][j+1], len);
}
}
rep(st, 2*M) {
rep(i, cs) dtemp[i] = 1e18;
dtemp[st] = 0;
priority_queue <pli, vector<pli>, greater<pli> > pq;
pq.push(pli(0, st));
while(!pq.empty()) {
pli t = pq.top(); pq.pop();
if(dtemp[t.Se] != t.Fi) continue;
for(pii e : E[t.Se]) {
if(t.Fi + e.Fi < dtemp[e.Se]) {
dtemp[e.Se] = t.Fi + e.Fi;
pq.push(pli(dtemp[e.Se], e.Se));
}
}
}
rep(i, 2*M) dis[st][i] = dtemp[i];
}
for(int i=1;i<=N;i++) for(int j=1;j<=N;j++) {
int si = szz(IE[i]);
int sj = szz(IE[j]);
vector <vector <plp> > mn[4];
vector <vector <ll> > val;
rep(a, 4) {
mn[a].resize(si);
val.resize(si);
rep(b, si) mn[a][b].resize(sj), val[b].resize(sj);
}
rep(k, si) {
int eidx = nume[i][k];
rep(l, sj) {
int fidx = nume[j][l] ^ 1;
plp pp = plp(dis[eidx][fidx] + get<2>(edgen[fidx]), pii(k, l));
rep(t, 4) mn[t][k][l] = pp;
val[k][l] = pp.Fi;
}
}
rep(k, si) for(int l=1;l<sj;l++) for(int a : {0, 2}) updplp(mn[a][k][l], mn[a][k][l-1]);
rep(k, si) for(int l=sj-2;l>=0;l--) for(int a : {1, 3}) updplp(mn[a][k][l], mn[a][k][l+1]);
rep(l, sj) for(int k=1;k<si;k++) for(int a : {0, 1}) updplp(mn[a][k][l], mn[a][k-1][l]);
rep(l, sj) for(int k=si-2;k>=0;k--) for(int a : {2, 3}) updplp(mn[a][k][l], mn[a][k+1][l]);
set <pii> Sx;
rep(k, si) rep(l, sj) {
plp r = plp(1e18, pii(-1, -1));
if(k > 0 && l > 0) updplp(r, mn[0][k-1][l-1]);
if(k > 0 && l < sj - 1) updplp(r, mn[1][k-1][l+1]);
if(k < si - 1 && l > 0) updplp(r, mn[2][k+1][l-1]);
if(k < si - 1 && l < sj - 1) updplp(r, mn[3][k+1][l+1]);
Sx.insert(r.Se);
}
rep(k, si) {
plp r = plp(1e18, pii(-1, -1));
if(k > 0) updplp(r, mn[0][k-1][sj-1]);
if(k < si - 1) updplp(r, mn[2][k+1][sj-1]);
Sx.insert(r.Se);
}
rep(l, sj) {
plp r = plp(1e18, pii(-1, -1));
if(l > 0) updplp(r, mn[0][si-1][l-1]);
if(l < sj - 1) updplp(r, mn[1][si-1][l+1]);
Sx.insert(r.Se);
}
plp r = plp(1e18, pii(-1, -1));
updplp(r, mn[0][si-1][sj-1]);
Sx.insert(r.Se);
for(pii e : Sx) if(e.Fi != -1) {
Idx[i][j].pb(pii(IE[i][e.Fi].Se, IE[j][e.Se].Se));
ll v = val[e.Fi][e.Se];
Val[i][j].pb(v);
}
}
for(int i=1;i<=L;i++) scanf("%d", X+i);
for(int i=1;i<=T;i++) {
int x, y; scanf("%d%d", &x, &y);
query[i] = pii(x, y);
}
Init(1, 1, L - 1);
for(int i=1;i<=T;i++) {
int x = query[i].Fi;
int y = query[i].Se;
X[x] = y;
if(x > 1) update(1, 1, L - 1, x - 1);
if(x < L) update(1, 1, L - 1, x);
ll val = Tr[1].Get();
if(val >= 1e18) puts("-1");
else printf("%lld\n", val);
}
return 0;
}
