Migrated from Lutece 2545 星际迷航

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

114514 年，人类的科技已经十分发达，星际旅行已变得十分容易。人类已经涉足的星球有地球（编号为 $1$）和其他 $n-1$ 颗星球（编号分别为 $2,3,\ldots ,n$），并在这些星球之间建立了 $m$ 条单向航线，支付一定的费用就可以乘坐航班通过这些路线。

目前市面上流通着两种货币：原石和摩拉。在编号为 $i$ 的星球，你可以用 $1$ 个原石兑换 $a_i$ 个摩拉（可以无限次兑换，因为原石比较珍贵，所以只能用原石兑换摩拉而不能用摩拉兑换原石）。星球之间的航行既可以用原石支付，也能用摩拉支付，具体来说，通过第 $j$ 条航线时，你可以用 $c_j$ 个原石或 $d_j$ 个摩拉支付。通过一条航线时只能选择一种支付方式，不能同时使用原石和摩拉支付，但对于不同航线，可使用不同的支付方式。

某一天，你决定从地球出发，到 $n$ 号星球去。你准备在出发前携带 $x$ 个原石，并在途中的某个星球（包括地球）将剩余的原石全部兑换为摩拉，然后继续旅行，直到达到目的地为止。当然，你也可以只使用原石完成旅行。

各地会经常调整汇率，既调整 $1$ 个原石能兑换摩拉的数量。现在你需要计算一下，每次汇率调整完后，完成旅程所需要准备原石数量 $x$ 的最小值。

Input

第一行给出三个正整数 $n\ (2\le n \le 10^5)$，$m\ (2\le m \le 2\times 10^5)$，$k\ (2\le k \le 10^5)$，分别代表星球数量，航线数量和汇率调整次数。

接下来 $m$ 行，第 $j$ 行包含四个正整数 $u_j,v_j\ (1\le u_j,v_j\le n,u_j\ne v_j),c_j,d_j\ (1\le c_j,d_j \le 10^9)$，表示第 $j$ 条航线从编号为 $u_j$ 的星球通向编号为 $v_j$ 的星球，可以使用 $c_j$ 个原石或 $d_j$ 个摩拉支付。数据保证从地球出发可以到达目的地。

接下来一行包含 $n$ 个正整数 $a_1,a_2,\dots ,a_n$，表示最初第 $i$ 个星球上的汇率为 $a_i$。

接下来 $k$ 行，第 $i$ 行包括两个正整数 $x_i\ (1\le x_i \le n),a_{i}^{\prime}\ (1\le a_{i}^{\prime} \le 10^9)$，表示第 $i$ 次汇率调整后编号为 $x_i$ 的星球上的汇率变成 $a_{i}^{\prime}$

Output

输出 $k$ 行，第 $i$ 行表示第 $i$ 次汇率调整后完成旅程所需要准备原石数量 $x$ 的最小值。

Samples

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

8
8
1

Resources

2021 UESTC ICPC Training for Graph