#P1288. 幻想过山车
幻想过山车
题目描述
阿瓦和阿卡一起来到了幻想游乐园。这座游乐园比较奇特,它的入口建在幻想山的悬崖上,它的出口建在图潇山的悬崖上,游乐园中的游乐设施之间只能够通过乘坐过山车来互相到达。
幻想游乐园一共有 个游乐设施,我们将人口编号为 出口编号为 。一共建了 条过山车道来连接两个游乐设施,第 条过山车道连接编号为 和 的两个游乐设施,乘坐它花费的时间为 。
阿瓦和阿卡觉得简单地坐过山车没什么意思,于是他们想出了一个有趣的问题: 能不能找到一种乘坐过山车的方式使得从起点到终点正好花费 分钟呢?
你可以经过一个游乐设施多次,也可以乘坐一条过山车多次,每次都计算时间。
输入格式
第一行两个数 , 表示游乐设施个数和过山车道的条数。
接下来 行, 第 行三个数 。
接下来一行一个数 , 表示询问个数。
接下来 行, 每行一个询问 。
输出格式
输出 行,对于每组询问,如果能够找到一种方式使得从起点到终点恰好花费 分钟,则输出一行 ,否则输出一行 。
样例输入输出
3 5
3 1 6
3 3 1
3 3 10
3 1 10
1 2 3
3
6
7
3
AWaDa!
AWaDa!
AKTang!
说明/提示
对于 的数据, 。
对于 的数据, 。
对于 的数据, $n, m \leq 10^{4}, Q \leq 10^{5}, P \leq 10^{9}, 0<u_{i}, v_{i} \leq n, 0<w_{i} \leq 50 $ 。