Money Transfers

Sonia is the CEO of the South Western Economic Research Consortium (SWERC). The main asset of SWERC is a group of banks spread out in several countries, which specialize in wire transfers between these countries.

Money is transferred between banks which have transfer agreements. Such agreements settle a fixed fee whenever there is a transfer between these banks. When a client wishes to transfer money to an account in a different bank, the money flows between banks with transfer agreements until it reaches the destination account. For each intermediary transaction, the client will have to pay the corresponding transfer fee.

SWERCâ€™s goal is to provide the cheapest fees for its clients, using only its banks as intermediaries, and profit from its commissions. Things were going quite well until the recent economic crisis. Due to the current situation, governments agreed to impose an extra tax on each wire transfer. Their objective is to both increase the tax income and avoid losing money to tax havens around the world. Hence, the intention is make this extra tax as large as possible (while avoiding too much unrest).

Sonia, being a savvy executive, wants to take advantage of
this situation and make sure SWERC provides the cheapest way to
transfer money between banks **X** and **Y** (their most frequent transfer requests). She will
try to lobby the politicians so that the new fee makes this
happen. She gathered data about the transfer agreements between
banks (including competitors) but has no idea what should be
the value of the new fee.

Can you help Sonia compute the largest fee so that SWERC can
provide cheapest way to transfer money between **X** and **Y**?

The first line consists of four space-separated integers:
$N$ $P$ $X$ $Y$, the number of existing banks, the
number of transfer partnerships, and the identifiers of banks
**X** and **Y**, respectively. The
next $P$ lines have three
space-separated integers: $a_
i$ $b_ i$
$c_ i$, meaning there is a
partnership between banks $a_
i$ and $b_ i$ with
fee $c_ i$.

A line with an integer $M$, the number of banks owned by SWERC, follows. The next line contains $M$ space-separated integers, the identifiers of these banks. $X$ and $Y$ are always in this list.

$2 \leq M \leq N \leq 1\, 000$ |
and |
$1 \leq P \leq 10\, 000$ |

$1 \leq X, Y, a_ i, b_ i \leq N$ |
and |
$X \neq Y$ and $a_ i \neq b_ i$ |

$1 \leq c_ i \leq 1\, 000\, 000\, 000$ |

The output should be a single integer greater than zero: the
largest fee so that SWERC can provide cheapest way to transfer
money between $X$ and
$Y$. However, if there is
no value such that this happens, output `Impossible` instead. If the fee on each transfer can
be infinitely large, output `Infinity`.

If the extra fee is 4 or more, then SWERC can not provide the cheapest transaction fee. Example: if the fee is 4, SWERC provides a cost of 20, using banks 1, 3, 4, 5 and 6, in this order. However, using bank 2 as an intermediary, we can pay only 19.

Sample Input 1 | Sample Output 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 |
3 |

Sample Input 2 | Sample Output 2 |
---|---|

3 4 1 2 1 2 6 1 3 2 1 2 7 2 3 3 2 1 2 |
Infinity |

Sample Input 3 | Sample Output 3 |
---|---|

4 4 1 4 1 2 1 1 3 1 2 4 1 3 4 1 3 1 2 4 |
Impossible |