도시 간 이동

몇 년 전만 해도 우크라이나 철도망은 아주 편리했다. 어느 두 도시 사이에도 직통 열차가 한 대씩 다녔고, 누구든 요금 $B$ 흐리브냐만 내면 지금 있는 도시에서 가고 싶은 도시로 갈 수 있었다.

최근 우크라이나에 큰 변화가 생겼다. 새 열차가 많이 도입되었다. 새 열차는 저마다 기존 열차 한 대를 대체했고, 요금은 $A$ 흐리브냐로 정해졌다. 그래서 지금도 두 도시 사이에는 직통 열차가 정확히 한 대씩 다닌다. 새 열차일 수도 있고 기존 열차일 수도 있다. 열차는 모두 양방향으로 운행하며, 요금은 방향과 무관하다.

우크라이나에는 큰 도시가 $N$개 있고, 당신은 1번 도시에 산다. $N$번 도시로 가려고 한다. 환승 횟수는 상관없으니, 요금의 합이 가장 적은 방법을 찾아라.

첫째 줄에 도시의 수 $N$, 새 열차의 수 $K$, 새 열차의 요금 $A$, 기존 열차의 요금 $B$가 정수로 주어진다. ($2 \le N \le 500000$, $0 \le K \le 500000$, $1 \le A, B \le 500000$)

다음 $K$개 줄에는 두 정수 $u_i$와 $v_i$가 주어진다. ($1 \le u_i, v_i \le N$) $u_i$번 도시와 $v_i$번 도시 사이에 새 열차가 다닌다는 뜻이다. $u_i$와 $v_i$는 서로 다르고, 같은 도시 쌍은 최대 한 번 등장한다.

1번 도시에서 $N$번 도시까지 가는 가장 싼 방법의 요금 $P$를 출력한다.