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 over several countries that specialize in wire transfers between those countries.

Money moves only between two banks that hold a transfer agreement. An agreement fixes the fee paid for every transfer that crosses it. When a client sends money to an account at another bank, the money passes through banks that hold agreements until it reaches the destination account, and the client pays the fee of every agreement it crosses.

SWERC wants to give clients the cheapest fee while using only its own banks as intermediaries, and to earn commissions in return. That worked well until the recent economic crisis. Because of the current situation, governments agreed to charge the same extra fee on every single transfer. They want to raise tax income and to keep money from leaking to tax havens, so they want this extra fee to be as large as they can make it without too much unrest.

Sonia wants to use the situation and make SWERC the cheapest way to send money between bank $X$ and bank $Y$, the pair she is asked about most often. She plans to lobby politicians for the extra fee that brings this about. She collected the agreement data, competitors included, but she does not know what the extra fee should be.

With an extra fee of $F$, a route that crosses $k$ agreements whose fees sum to $w$ costs $w + k \times F$. SWERC gives the cheapest way when the cheapest route from $X$ to $Y$ whose intermediate banks all belong to SWERC is strictly cheaper than every route that passes through at least one bank outside SWERC. A tie does not count as giving the cheapest way.

Compute the largest extra fee for which SWERC gives the cheapest way to send money from $X$ to $Y$.

The first line has four space separated integers $N$, $P$, $X$, $Y$: the number of banks, the number of transfer agreements, and the identifiers of the two banks.

Each of the next $P$ lines has three space separated integers $a_i$, $b_i$, $c_i$, meaning that banks $a_i$ and $b_i$ hold an agreement with fee $c_i$. The same pair of banks may hold several agreements.

The next line has $M$, the number of banks owned by SWERC. The line after it has the $M$ identifiers of those banks, separated by spaces. $X$ and $Y$ are always on this list.

Print one integer greater than zero: the largest extra fee for which SWERC gives the cheapest way to send money from $X$ to $Y$.

If no such value exists, print Impossible instead. If the condition holds no matter how large the extra fee gets, print Infinity.

• $2 \le M \le N \le 1000$, $1 \le P \le 10000$
• $1 \le X, Y, a_i, b_i \le N$, $X \ne Y$, $a_i \ne b_i$
• $1 \le c_i \le 10^9$

In the first example an extra fee of 4 or more stops SWERC from giving the cheapest route. With a fee of 4 SWERC reaches a cost of 20 through banks 1, 3, 4, 5 and 6 in that order, while a route through bank 2 costs only 19.