typedef pair<long long, int> PII;
int n, m, q;
int head1[maxn], head2[maxn];
ll dis1[maxn], dis2[maxn];
struct node {
int v, to, nex;
int w;
}e[maxn << 2];
int idx;
multiset<ll> mst;
void init() {
idx = 0;
memset(head1, -1, sizeof head1);
memset(head2, -1, sizeof head2);
}
void add(int h[], int u, int v, int w) {
e[idx].v = v;
e[idx].nex = h[u];
e[idx].w = w;
h[u] = idx++;
}
bool vis[maxn];
void dij(ll dis[], int head[], int st) {
memset(dis, 0x3f3f3f3f3f3f3f3f, sizeof dis1);
memset(vis, 0, sizeof vis);
priority_queue <PII, vector<PII>, greater<PII> > que;
que.push({ 0,st });
dis[st] = 0;
while (que.size()) {
int u = que.top().second;
que.pop();
if (vis[u]) continue;
vis[u] = 1;
for (int i = head[u]; ~i; i = e[i].nex) {
// cout << e[i].v << endl;
int to = e[i].v;
if (dis[to] > dis[u] + e[i].w) {
dis[to] = dis[u] + e[i].w;
que.push({ dis[to],to });
}
}
}
}
int a[maxn];
void getAns() {
for (int i = 1; i <= n; i++) {
if (dis1[i] == 0x3f3f3f3f3f3f3f3f) continue;
if (dis2[i] == 0x3f3f3f3f3f3f3f3f) continue;
ll val = dis1[i] + (dis2[i] + a[i] - 1) / a[i];
mst.insert(val);
// puts("add");
}
for (int qq = 1; qq <= q; qq++) {
// puts("qq");
int x = read, aa = read;
if (dis1[x] != 0x3f3f3f3f3f3f3f3f && dis2[x] != 0x3f3f3f3f3f3f3f3f) {
ll t = dis1[x] + (dis2[x] + a[x] - 1) / a[x];
mst.erase(mst.find(t));
a[x] = aa;
ll val = dis1[x] + (dis2[x] + aa - 1) / aa;
mst.insert(val);
}
printf("%lld\n", *mst.begin());
}
}
int main() {
n = read, m = read, q = read;
init();
memset(dis1, 0x3f3f3f3f3f3f3f3f, sizeof dis1);
memset(dis2, 0x3f3f3f3f3f3f3f3f, sizeof dis2);
for (int i = 1; i <= m; i++) {
int u = read, v = read, c = read, d = read;
add(head1, u, v, c);
add(head2, v, u, d);
}
for (int i = 1; i <= n; i++) a[i] = read;
dij(dis1, head1, 1);
dij(dis2, head2, n);
/*
for (int i = 1; i <= n; i++) {
cout << dis1[i] << " " << dis2[i] << endl;
}*/
getAns();
return 0;
}
/**
6 11 3
1 2 3 5
1 3 8 4
2 4 4 6
3 1 8 6
1 3 10 8
2 3 2 8
3 4 5 3
3 5 10 7
3 3 2 3
4 6 10 12
5 6 10 6
3 4 5 2 5 100
1 2
2 1
1 17
**/
