업고 가기

베시와 동생 엘시는 낮에 서로 다른 목초지에서 풀을 뜯고, 저녁이 되면 둘 다 헛간으로 돌아가 쉬려고 한다. 두 소는 걸어서 돌아가는 데 쓰는 에너지의 합을 가장 작게 만들고 싶다.

베시는 인접한 목초지로 한 번 걸어갈 때마다 에너지 $B$를 쓰고, 엘시는 같은 이동에 에너지 $E$를 쓴다. 두 소가 같은 목초지에 함께 있으면 베시가 엘시를 어깨에 업을 수 있고, 이때 둘은 인접한 목초지로 함께 이동하면서 에너지를 합쳐 $P$만 쓴다. $P$는 $B + E$보다 훨씬 작을 수도 있다. 그런 경우에는 둘이 먼저 같은 목초지에서 만난 다음 남은 길을 업고 가는 방법이 가장 적게 드는 계획이 된다. 반대로 $P$가 크면 끝까지 따로 걸어가는 편이 더 적게 드는 경우도 있다.

$B$, $E$, $P$와 농장의 구조가 주어질 때, 베시와 엘시가 헛간에 도착하기 위해 써야 하는 에너지 합의 최솟값을 구하시오.

첫째 줄에 양의 정수 $B$, $E$, $P$, $N$, $M$이 공백으로 구분되어 주어진다. 다섯 값은 모두 40000 이하이다. $N$은 목초지의 개수이고 목초지에는 1번부터 $N$번까지 번호가 붙어 있으며 $N \ge 3$이다. $M$은 목초지 사이를 잇는 통로의 개수이다. 베시는 1번 목초지에서, 엘시는 2번 목초지에서 출발하고, 헛간은 $N$번 목초지에 있다.

다음 $M$개의 줄에는 각각 서로 다른 두 목초지의 번호가 주어지며, 그 두 목초지를 잇는 통로 하나를 뜻한다. 통로는 양방향으로 지나갈 수 있다. 1번 목초지에서 $N$번 목초지로, 2번 목초지에서 $N$번 목초지로 통로를 따라 이동하는 방법은 항상 존재한다.

베시와 엘시가 헛간에 도착하기 위해 함께 쓰는 에너지 합의 최솟값을 정수 하나로 출력한다.