{"raw_statement":[{"iden":"statement","content":"在 JOI 王国中，有 $n$ 个城市，编号从 $1$ 到 $n$。JOI 王国有 $n−1$ 条双向道路，编号从 $1$ 到 $n−1$。第 $i$ 条道路连接城市 $a_i$ 和城市 $b_i$。\n\n在 JOI 王国中，一些道路上放有检查站。有 $m$ 个检查站，编号从 $1$ 到 $m$。第 $j$ 个检查站位于道路 $p_j$ 上。通过该检查站需要支付 $1$ 枚金币或 $c_j$ 枚银币。\n\n在 JOI 王国有 $q$ 名公民，编号从 $1$ 到 $q$。第 $k$ 名公民持有 $x_k$ 枚金币和 $y_k$ 枚银币，并希望从城市 $s_k$ 前往城市 $t_k$。由于金币具有较高的价值，所有公民都希望尽可能多地保留金币。\n\n编写一个程序，给定 JOI 王国中的城市、道路、检查站和公民信息，对于每个 $k (1≤k≤q)$，判断公民 $k$ 是否能够从城市 $s_k$ 前往城市 $t_k$，并在此条件成立时计算公民 $k$ 所能保留的最多金币数。"},{"iden":"input","content":"从标准输入读入以下数据。\n> $N \\ M \\ Q$\n>\n> $A_1 \\ B_1$\n>\n> $A_2 \\ B_2$\n>\n> $\\vdots$\n>\n> $A_{N - 1} \\ B_{N - 1}$\n>\n> $P_1 \\ C_1$\n>\n> $P_2 \\ C_2$\n>\n> $\\vdots$\n>\n> $P_M \\ C_M$\n>\n> $S_1 \\ T_1 \\ X_1 \\ Y_1$\n>\n> $S_2 \\ T_2 \\ X_2 \\ Y_2$\n>\n> $\\vdots$\n>\n> $S_Q \\ T_Q \\ X_Q \\ Y_Q$"},{"iden":"output","content":"向标准输出打印 $q$ 行。在第 $k$ 行 $(1≤k≤q)$ 中，如果公民 $k$ 可以从城市 $s_k$ 前往城市 $t_k$，请输出公民 $k$ 可以保留的最多金币数。否则，在第 $k$ 行中输出 $−1$。\n\nTranslate by @[ZeXic_B](https://www.luogu.com.cn/user/661274)"},{"iden":"note","content":"数据范围：$2\\le N\\le 10^5$，$1\\le M,Q\\le 10^5$，$1\\le A_i,B_i\\le N$，$1\\le P_i\\le N-1$，$1\\le C_j\\le 10^9$，$1\\le S_k,T_k\\le N$，$S_k\\neq T_k$，$0\\le X_k\\le 10^9$，$0\\le Y_k\\le 10^{18}$，所有数都是整数，所有城市连通。\n\nSubtasks：\n- Subtask 1（10 分）：$N,M,Q\\le 2000$。\n- Subtask 2（28 分）：$C_1=C_2=\\cdots=C_M$。\n- Subtask 3（30 分）：$A_i=i$，$B_i=i+1$。\n- Subtask 4（32 分）：无特殊限制。"}],"translated_statement":null,"sample_group":[["5 4 3\n1 2\n1 3\n2 4\n2 5\n2 9\n2 4\n3 5\n4 7\n3 4 2 11\n5 3 4 5\n2 3 1 1\n","1\n2\n-1\n"],["10 7 9\n1 8\n6 3\n5 9\n7 9\n3 1\n3 4\n10 1\n2 6\n5 6\n9 4\n7 4\n7 4\n2 4\n7 4\n7 4\n1 4\n8 6 5 3\n3 9 8 0\n4 7 6 15\n7 4 9 3\n6 4 8 0\n9 10 5 16\n5 3 2 4\n2 8 4 3\n6 1 3 3\n","3\n6\n6\n7\n7\n3\n1\n2\n2\n"],["8 7 11\n1 2\n2 3\n3 4\n4 5\n5 6\n6 7\n7 8\n4 4\n3 7\n2 10\n5 2\n4 1\n4 4\n5 6\n6 3 7 69\n7 1 5 55\n3 1 6 8\n8 2 5 45\n4 6 4 45\n6 1 3 33\n2 1 0 19\n3 7 2 31\n7 1 2 31\n7 2 4 58\n8 3 5 63\n","7\n5\n5\n5\n4\n2\n0\n2\n1\n4\n5\n"],["8 7 11\n1 8\n1 4\n3 1\n3 6\n6 7\n2 1\n5 2\n5 5\n5 8\n4 7\n6 6\n4 1\n6 4\n1 7\n4 7 2 18\n2 4 5 1\n4 2 1 32\n1 5 7 21\n2 5 0 50\n8 4 4 33\n1 7 6 16\n4 8 7 18\n1 2 8 13\n5 4 10 42\n7 1 6 40\n","1\n3\n1\n7\n0\n4\n5\n7\n8\n10\n6"]],"show_order":[],"formal_statement":null,"simple_statement":null,"has_page_source":false}