Sonia 是西南经济研究联盟 (SWERC) 的首席执行官。SWERC 的主要资产是一组分布在多个国家的银行,这些银行专门从事这些国家之间的电汇业务。
银行之间通过转账协议进行资金转移。每当这些银行之间发生转账时,此类协议都会确定一笔固定费用。当客户希望将资金转账到不同银行的账户时,资金会在有转账协议的银行之间流动,直到到达目标账户。对于每一笔中间交易,客户都必须支付相应的转账费用。
SWERC 的目标是仅使用其旗下的银行作为中介,为客户提供最便宜的费用,并从中赚取佣金。在最近的经济危机之前,一切进展顺利。由于当前形势,各国政府同意对每笔电汇征收额外税款。他们的目标既是增加税收收入,又避免资金流向世界各地的避税天堂。因此,他们的意图是尽可能提高这笔额外税款(同时避免引起过多的动荡)。
Sonia 是一位精明的执行官,她想利用这种情况,确保 SWERC 提供在银行 $X$ 和 $Y$(他们最频繁的转账请求)之间转账的最便宜方式。她将尝试游说政客,以便新的费用能实现这一目标。她收集了关于银行之间(包括竞争对手)转账协议的数据,但不知道新费用的数值应该是多少。
任务
你能帮助 Sonia 计算出最大的费用,使得 SWERC 能够提供在 $X$ 和 $Y$ 之间转账的最便宜方式吗?
输入格式
第一行包含四个空格分隔的整数:$N, P, X, Y$,分别表示现有银行的数量、转账合作关系的数量以及银行 $X$ 和 $Y$ 的标识符。接下来的 $P$ 行包含三个空格分隔的整数:$a_i, b_i, c_i$,表示银行 $a_i$ 和 $b_i$ 之间存在费用为 $c_i$ 的合作关系。
随后是一行包含一个整数 $M$,表示 SWERC 拥有的银行数量。下一行包含 $M$ 个空格分隔的整数,即这些银行的标识符。$X$ 和 $Y$ 总是在此列表中。
数据范围
$2 \le M \le N \le 1\,000$ 且 $1 \le P \le 10\,000$ $1 \le X, Y, a_i, b_i \le N$ 且 $X \neq Y$ 且 $a_i \neq b_i$ $1 \le c_i \le 1\,000\,000\,000$
输出格式
输出应为一个大于零的整数:使得 SWERC 能够提供在 $X$ 和 $Y$ 之间转账的最便宜方式的最大费用。但是,如果没有这样的值可以实现这一点,则输出 Impossible。如果每笔转账的费用可以无限大,则输出 Infinity。
样例
输入格式 1
6 8 1 6 1 2 5 1 3 1 2 6 6 2 3 6 4 2 3 3 4 1 4 5 1 5 6 1 5 1 3 6 5 4
输出格式 1
3
说明
如果额外费用为 4 或更多,则 SWERC 无法提供最便宜的交易费用。例如:如果费用为 4,SWERC 提供的成本为 20,依次使用银行 1、3、4、5 和 6。然而,使用银行 2 作为中介,我们只需支付 19。
输入格式 2
3 4 1 2 1 2 6 1 3 2 1 2 7 2 3 3 2 1 2
输出格式 2
Infinity
输入格式 3
4 4 1 4 1 2 1 1 3 1 2 4 1 3 4 1 3 1 2 4
输出格式 3
Impossible