#include<bits/stdc++.h>
using namespace std;
//1 cash 2 paper
#define PII pair<long long,int>
const int N = 400010;
int no[N],va[N],ne[N],h1[N],h2[N],idx;
int rate[N];
long long dist1[N];
bool st1[N];
long long dist2[N];
bool st2[N];
int n,m,q;
void add1(int a,int b,int c)
{
no[idx] = b,va[idx] = c,ne[idx] = h1[a],h1[a] = idx,idx++;
}
void add2(int a,int b,int d)
{
no[idx] = b,va[idx] = d,ne[idx] = h2[a],h2[a] = idx,idx++;
}
void dijkstra1()
{
memset(dist1,0x3f,sizeof dist1);
dist1[1] = 0;
priority_queue<PII,vector<PII>,greater<PII>> queue;
queue.push({0,1});
for(int i = 1;i <= n;++i)
st1[i] = false;
while(queue.size() > 0)
{
PII t = queue.top();
queue.pop();
int ver = t.second;
if(st1[ver]) continue;
st1[ver] = true;
for(int i = h1[ver];i != -1;i = ne[i])
{
int j = no[i];
if(dist1[j] > dist1[ver] + va[i])
{
dist1[j] = dist1[ver] + va[i];
queue.push({dist1[j],j});
}
}
}
}
void dijkstra2()
{
memset(dist2,0x3f,sizeof dist2);
dist2[n] = 0;
priority_queue<PII,vector<PII>,greater<PII>> queue;
queue.push({0,n});
for(int i = 1;i <= n;++i)
st2[i] = false;
while(queue.size() > 0)
{
PII t = queue.top();
queue.pop();
int ver = t.second;
if(st2[ver]) continue;
st2[ver] = true;
for(int i = h2[ver];i != -1;i = ne[i])
{
int j = no[i];
if(dist2[j] > dist2[ver] + va[i])
{
dist2[j] = dist2[ver] + va[i];
queue.push({dist2[j],j});
}
}
}
}
int main()
{
memset(h1,-1,sizeof h1);
memset(h2,-1,sizeof h2);
cin>>n>>m>>q;
int a,b,c,d;
for(int i = 0;i < m;++i)
{
// cin>>a>>b>>c>>d;
scanf("%d %d %d %d",&a,&b,&c,&d);
add1(a,b,c);
add2(b,a,d);
}
dijkstra1();
dijkstra2();
for(int i = 1;i <= n;++i)
scanf("%d",&rate[i]);
multiset<long long> s;
for(int i = 1;i <= n;++i)
if(dist1[i] != 0x3f3f3f3f3f3f3f3f && dist2[i] != 0x3f3f3f3f3f3f3f3f)
s.insert(dist1[i] + (dist2[i] + rate[i] - 1) / rate[i]);
for(int i = 0;i < q;++i)
{
cin>>a>>b;
if(dist1[a] != 0x3f3f3f3f3f3f3f3f && dist2[a] != 0x3f3f3f3f3f3f3f3f)
{
s.erase(s.find(dist1[a] + (dist2[a] + rate[a] - 1) / rate[a]));
rate[a] = b;
s.insert(dist1[a] + (dist2[a] + rate[a] - 1) / rate[a]);
}
cout<<*s.begin()<<endl;
}
return 0;
}