송금 수수료

소니아는 남서부 경제 연구 컨소시엄(SWERC)의 대표다. SWERC의 핵심 자산은 여러 나라에 흩어져 있는 은행 집단이고, 이 은행들은 국가 간 송금을 전문으로 다룬다.

송금은 송금 협약을 맺은 두 은행 사이에서만 오간다. 협약에는 그 구간을 지나는 송금 한 건마다 내야 하는 고정 수수료가 정해져 있다. 고객이 다른 은행의 계좌로 돈을 보내면 돈은 협약을 맺은 은행을 차례로 거쳐 목적지 계좌에 도달하고, 고객은 거친 구간마다 그 구간의 수수료를 낸다.

SWERC는 자기 은행만 중간 경로로 써서 고객에게 가장 싼 수수료를 제공하고 그 대가로 수입을 얻으려 한다. 최근 경제 위기가 오기 전까지는 계획대로 굴러갔다. 지금 상황 때문에 각국 정부는 송금 한 건마다 같은 액수의 추가 수수료를 매기기로 합의했다. 세수를 늘리면서 돈이 조세 회피처로 새어 나가는 것을 막자는 것이 목표라서, 정부는 불만이 너무 커지지 않는 선에서 이 추가 수수료를 최대한 크게 잡으려 한다.

소니아는 이 상황을 이용해 요청이 가장 많은 구간인 $X$ 은행과 $Y$ 은행 사이 송금을 SWERC가 가장 싸게 처리하도록 만들고 싶다. 그렇게 되는 추가 수수료 값을 정치인에게 로비할 계획이다. 경쟁 은행까지 포함한 협약 자료는 모아 두었지만 추가 수수료를 얼마로 잡아야 하는지는 모른다.

추가 수수료가 $F$일 때, 협약 $k$개를 지나고 협약 수수료의 합이 $w$인 경로의 비용은 $w + k \times F$이다. SWERC가 가장 싼 경로를 제공한다는 것은, 양 끝을 뺀 중간 은행이 모두 SWERC 소유인 $X$에서 $Y$로 가는 경로 중 가장 싼 것이 SWERC 소유가 아닌 은행을 하나라도 거치는 모든 경로보다 엄밀하게 싸다는 뜻이다. 비용이 같으면 SWERC가 가장 싼 경로를 제공한 것으로 보지 않는다.

SWERC가 $X$에서 $Y$로 가는 가장 싼 경로를 제공하게 되는 가장 큰 추가 수수료를 구하라.

첫 줄에 정수 네 개 $N$, $P$, $X$, $Y$가 공백으로 구분되어 주어진다. $N$은 은행 수, $P$는 송금 협약 수이고 $X$와 $Y$는 두 은행의 번호다.

다음 $P$개의 줄에는 정수 세 개 $a_i$, $b_i$, $c_i$가 주어진다. 은행 $a_i$와 $b_i$ 사이에 수수료 $c_i$의 협약이 있다는 뜻이다. 같은 두 은행 사이에 협약이 여러 개 있을 수 있다.

그다음 줄에 SWERC가 소유한 은행의 수 $M$이 주어진다. 이어지는 줄에 그 은행의 번호 $M$개가 공백으로 구분되어 주어진다. $X$와 $Y$는 항상 이 목록에 들어 있다.

SWERC가 $X$에서 $Y$로 가는 가장 싼 경로를 제공하게 되는 가장 큰 추가 수수료를 0보다 큰 정수 하나로 출력한다.

그런 값이 하나도 없으면 Impossible을 출력한다. 추가 수수료를 얼마든지 크게 잡아도 조건이 성립하면 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$

첫 번째 예제에서 추가 수수료가 4 이상이면 SWERC는 가장 싼 경로를 제공하지 못한다. 수수료가 4일 때 SWERC는 은행 1, 3, 4, 5, 6을 이 순서로 거쳐 비용 20을 만들지만, 은행 2를 중간에 쓰면 19만 내면 된다.