등산

주환이는 요즘 등산에 빠졌다. 주환이는 등산을 위해 지도를 가지고 있는데, 그 지도에는 각 지점의 높이와 갈 수 있는 다른 지점까지의 거리가 표시되어 있다.

주환이는 아침에 집에서 출발하여 등산을 갔다가, 오후 수업을 듣기 위해 고려대학교로 돌아와야 한다.

1. 주환이는 지도의 임의의 지점을 골라, 그 지점을 목표로 정한다. 집 또는 고려대학교는 목표로 선택할 수 없다.
2. 주환이가 집에서 정한 목표에 도달할 때까지는 항상 높이가 증가하는 방향으로만 이동해야 한다.
3. 주환이가 정한 목표에 도달한 후, 고려대학교로 갈 때에는 항상 높이가 감소하는 방향으로만 이동해야 한다.
4. 주환이는 거리 1을 움직일 때마다 $D$의 체력이 소모된다.
5. 주환이는 정한 목표에 도달하면 높이 1당 $E$의 성취감을 얻는다. 즉 높이가 $h$인 목표에 도달하면 $hE$의 성취감을 얻는다.

주환이는 이 등산의 가치를 (얻은 성취감) - (소모한 체력) 으로 계산하기로 하였다. 주환이를 위해 가치가 가장 높은 등산 경로를 선택해주자.

첫 번째 줄에 지도에 표시된 지점의 개수, 지점을 잇는 경로의 개수, 주환이의 거리 비례 체력 소모량, 높이 비례 성취감 획득량을 나타내는 정수 $N$, $M$, $D$, $E$가 공백을 사이에 두고 주어진다. (2 ≤ $N$ ≤ 100,000, 1 ≤ $M$ ≤ 200,000, 1 ≤ $D$ ≤ 100, 1 ≤ $E$ ≤ 100)

두 번째 줄에 $N$개의 정수 $h_1, ... ,h_N$이 공백으로 구분되어 주어진다. $h_i$는 $i$번째 지점의 높이를 의미한다. (1 ≤ $h_i$ ≤ 1,000,000, 1 ≤ $i$ ≤ $N$)

세 번째 줄부터 $M$개의 줄에 걸쳐 세 정수 $a, b, n$이 공백으로 구분되어 주어진다. 이는 $a$번 지점과 $b$번 지점을 잇는 거리 $n$의 양방향 경로가 있음을 의미한다. (1 ≤ $a, b$ ≤ $N$, 1 ≤ $n$ ≤ 100,000)

어떤 지점에서 다른 지점으로 가는 경로가 여러 개 있을 수도 있으며 (등산로는 여러 개가 있을 수 있다), 한 지점에서 출발해 그 지점으로 돌아가는 경로가 있을 수도 있다 (쉼터에서 몇 바퀴 돌며 쉴 수도 있다).

주환이의 집은 1번 지점에 위치하고, 고려대학교는 $N$번 지점에 위치하며 주환이의 집과 고려대학교의 높이는 1임이 보장된다.

첫 번째 줄에 주환이가 얻을 수 있는 가치의 최댓값을 출력한다. 만약 조건을 만족하는 등산 경로를 선택할 수 없다면, Impossible을 출력한다. 답이 음수일 수 있음에 유의하여라.