#P18061. Bobs Rating

Bobs Rating

Bobs Rating

给定一个有 NN 个顶点、MM 条边的无向图。第 ii 条边连接 Ui,ViU_i,V_i,通行所需的评级为 WiW_i。图可能不连通,允许自环和重边。

Bob 可以任意重复经过边、访问顶点。当且仅当他的当前评级至少为 WiW_i 时,他才能经过第 ii 条边;经过边不会消耗评级。

当 Bob 位于顶点 xx 时,可以进行以下操作:

  • 免费增加 AxA_x 点评级。在一次旅程中,每个顶点的这项免费奖励只能领取一次;不同顶点的免费奖励分别计算。
  • 花费 CxC_x 枚金币增加 11 点评级。这项操作可以重复任意次。

有 QQ 次相互独立的询问。第 ii 次询问中,Bob 初始位于 SiS_i,评级为 RiR_i,希望到达 TiT_i。求所需的最少金币数。出发时也可以领取起点的免费奖励。

如果无论花费多少金币都不能到达目标,输出 −1-1。

输入格式

第一行一个整数 TT,表示测试用例数。

每组数据包含:

  • 第一行三个整数 N,M,QN,M,Q。
  • 第二行 NN 个整数 A1,…,ANA_1,\ldots,A_N。
  • 第三行 NN 个整数 C1,…,CNC_1,\ldots,C_N。
  • 接下来 MM 行,每行三个整数 Ui,Vi,WiU_i,V_i,W_i。
  • 接下来 QQ 行,每行三个整数 Si,Ti,RiS_i,T_i,R_i。

输出格式

每组数据输出 QQ 行,每行一个整数,依次回答各次询问。

数据范围

1≤T≤1001\le T\le100,1≤N,M,Q≤5⋅1051\le N,M,Q\le5\cdot10^5,1≤Ai,Ci≤1061\le A_i,C_i\le10^6,1≤Wi,Ri≤10121\le W_i,R_i\le10^{12}。

所有顶点编号在 11 到 NN 之间。跨所有测试用例,∑N\sum N、∑M\sum M、∑Q\sum Q 各自不超过 5⋅1055\cdot10^5。

样例

1
5 5 4
5 2 4 3 10
1 2 3 4 5
3 3 10
1 2 5
3 4 7
1 3 13
2 5 21
4 5 3
2 2 4
1 4 2
5 2 10
11
0
4
5