Gothenburg의 언덕

대부분의 학생이 알고 있듯이, Gothenburg에는 어느 방향으로 가든 어째서인지 내리막길보다 오르막길이 더 많은 것처럼 보인다. 이 사실을 알고 있었기에 Lazy Smurf은 Smurfette에게 가던 도중 도심 한가운데에서 자전거가 고장 나자 더욱 절망했다. 자전거는 내리막길에서는 잘 달릴 수 있었지만, 페달이 고장 났기 때문에 오르막길에서는 자전거를 끌고 걸어야 했다. 이제 Lazy Smurf가 오르막길을 걷는 거리를 최소화하여 Smurfette에게 가는 경로를 찾을 수 있도록 여러분이 도와야 한다.

모두가 알다시피, Gothenburg 전체는 그래프 (https://en.wikipedia.org/wiki/Graph_(discrete_mathematics))로 나타낼 수 있다: $N$개의 지점(번호는 $1$부터 $N$까지)과 $M$개의 도로가 있으며 (각 도로는 두 지점을 직접 연결한다), 도시의 각 지점에는 알려진 높이 $h_i$가 있다. 지점 $i$과 $j$ 사이에 직접 연결된 도로가 있다면, 높이 차이 $h_i-h_j$가 양수일 경우 걸어야 하는 오르막 거리이다. Lazy Smurf이 자전거를 끌고 걸어야 하는 거리를 최소화하기 위해, 두 위치 사이의 모든 도로에 대한 높이 차이의 합을 최소화하는, 그의 위치에서 Smurfette의 위치까지의 경로를 찾고자 한다. 이때 내리막길과 평평한 도로는 $0$로 계산한다.

첫 번째 줄에는 사이에 공백이 있는 두 수 $N$과 $M$가 주어진다. $N$은 도시의 지점 수이고, $M$은 도로의 수이다. $1 \le N, M \le 10^5$

두 번째 줄에는 공백으로 구분된 두 수가 주어진다. 첫 번째 수는 Lazy Smurf이 있는 지점이고, 두 번째 수는 Smurfette가 있는 지점이다.

세 번째 줄에는 공백으로 구분된 $N$개의 수가 주어진다. 수 $h_i$ ($1 \le i \le N$)는 $i$번째 지점의 높이를 나타낸다. 항상 $-10^5 \le h_i \le 10^5$이다.

이어지는 $M$개의 각 줄에는 두 수 $i$과 $j$가 주어지며, 이는 지점 $i$과 지점 $j$ 사이에 도로가 있음을 의미한다. $i \ne j$이며, 모든 도로는 정확히 한 번씩 주어진다.

Lazy Smurf이 Smurfette에게 가기 위해 이동해야 하는 오르막 거리의 최솟값을 하나의 수로 출력한다.

첫 번째 예제에서 최적의 경로는 1-2-4로 가는 것이며, 이 경로의 총 오르막 거리는 $1+0=1$이다. 대신 경로 1-3-4을 이용했다면 총 오르막 거리는 $0+2=2$이었을 것이다.

두 번째 예제에서 1-7-6-5는 최소 오르막 거리 $0+4+3=7$를 갖는 경로의 한 예이다. 오르막 거리가 $7$인 또 다른 가능한 경로는 1-7-4-5이다. 다른 오르막 거리를 갖는 경로의 예로는 1-2-3-4-5이 있으며, 이 경로의 오르막 거리는 $0+3+0+6 = 9$이다.