阳光长跑

> 山田本一是日本八十年代的一名马拉松运动员，曾连续2次获得世界冠军，他在他的自传中这么说:"每次比赛之前，我都要乘车把比赛的线路仔细看一遍，并把沿途比较醒目的标志画下来，比如第一个标志是银行,第二个标志是一棵大树，第三个标志是一座红房子，这样一直画到赛程的终点。比赛开始后，我就以百米冲刺的速度奋力向第一个目标冲去，等到达第一个目标，我又以同样的速度向第二个目标冲去。四十几公里的赛程，就被我分解成这么几个小目标轻松地跑完了。"

众所周知，猛男小辣每天上完课后都会积极参与阳光长跑。他将学校划分成 $n$ 个标志点(编号从 $1$ 到 $n$)，其中 $4$ 个是打卡点，有 $m$ 条双向路径(编号从 $1$ 到 $m$)，每条路径连接两个标志点。

官方规定路线只有四条，依次是打卡点 $1$ 与打卡点 $2$ 之间，打卡点 $2$ 与打卡点 $3$ 之间，打卡点 $3$ 与打卡点 $4$ 之间，打卡点 $4$ 与打卡点 $1$ 之间，所经过路线的官方距离总和大于等于 2000m 这次阳光长跑才被记作有效。

因为刚下课，阳光长跑的同学很多，导致小辣的速度不及巅峰。我们假设小辣经过一条路径的时间 $= ($ 这条路上的人数 $+ 1) \times$ 这条路的距离。

随着时间的推移，路上的人会逐渐减少。小辣会依次收到 $q$ 条情报，声称某条路上的人数减少了，如果情报显示路上的人减少为负数，小辣认为这条路上的人数为 0

为了达到要求的配速，小辣希望你根据情报实时告诉他最快多久能完成长跑。小辣可以选择任意起点和任意终点。

第一行 $T$,表示数据组数

对于每组数据 第一行 $3$ 个整数 $n,m,q$

接下来一行 $4$ 个互不相同的整数表示 $n$ 个标志点中打卡点的编号

接下来一行 $4$ 个整数依次给出官方路线的距离,保证距离是 $2000$ 的因数

接下来 $m$ 行每行 $4$ 个整数 $u, v, d, p$ 表示 一条连接 $u,v$ 的路，距离为 $d$, 初始有 $p$ 人

接下来 $q$ 行每行 $2$ 个整数 $id, p$ 表示第 $i$ 条路上的人减少了 $p$ 个

$T \leq 10, 4 \leq n, q \leq 2\times 10^2, n - 1 \leq m \leq \frac{n(n-1)}{2}, 1 \leq d,p \leq 2000$

保证联通，没有重边,自环

对于每次修改输出一行一个整数，表示完成阳光长跑需要的最短时间

1
4 4 4
1 2 3 4
2000 2000 2000 2000
1 2 650 99
2 3 730 99
3 4 530 99
4 1 410 99
1 10
1 40
2 100
3 2000

41000
32500
730
530

杭州电子科技大学第二十二届程序设计竞赛