P9618 地铁

> 两年级生 孤单一人 > > 仰望上空 陋市苍穹 > > 在宇宙这个约会室中 > > Maybe 我们只是刚好没能邂逅呢

著名工程学专家 625OutContradiction 设计了一张地铁交通网 $G$．$G$ 拥有 $n$ 个站点和 $m$ 条地铁线路． 第 $i$ 条地铁线路 $P_i$ 会经过交通网上的若干站点，形如 $P_i=(u_1,u_2,u_3,...,u_{k_i})(k_i>0)$：每两个相邻站点 $u_j,u_{j+1}(j

第一行三个整数 $n, m, q$． 接下来 $m$ 行，第 $i$ 行形如：$k_i,u_1,u_2,u_3,...,u_{k_i}$． 表示一条地铁线路． 接下来 $q$ 行，每行三个整数，表示 $a,b,c$．

$q$ 行，对应每个问题的回答．

### 样例 #1 说明 $1\rightarrow 2\rightarrow 3\rightarrow 4\rightarrow 5$ 是给出的第一条地铁线路，$1\rightarrow 3$，$2\rightarrow 4\rightarrow 5$ 是第二三条地铁线路． 对于第一二组询问，均存在一种最优的出行方案为，在 $1$ 站点搭乘第二条地铁线路到达 $3$ 站点，在 $3$ 站点换乘第一条地铁线路到达终点；共经过 $3$ 段地铁轨道，并进行了 $1$ 次换乘，故第一二组询问的答案分别为 $3\times 1+1\times 1=4$，$3\times 3+1\times 0=9$．对于第三组询问，由于换乘的代价较大，最优的方案为顺着第一条地铁线路一直通向终点，途径 $4$ 段地铁轨道，答案为 $4$． ### 数据点约束 对于所有数据满足： $1\le n \le 10^5$，$1\le m \le 10^4$，$1\le q \le 10^5$，$\sum k_i \le 3\times 10^5$． $0 \le a,b \le 10^6$，$0 \le c \le 20$． --- 对于 $10\%$ 的数据满足：$n \le 20$，$\sum k_i \le 40$，$q \le 30$． --- 对于另外 $20\%$ 的数据满足：$c=0$． --- 对于另外 $30\%$ 的数据满足：$q=1$． --- 题目中可能存在只经过一个地铁站的地铁线路．这种线路可以直接忽视．数据保证：对于任意一组询问，存在一条合法的路线可以到达终点．