Tuấn và Mai là hai bạn cùng lớp. Hằng ngày, cả hai đi từ nhà tới trường của mình theo con đường tốn ít chi phí nhất (có thể có nhiều con đường đi tốn chi phí bằng nhau và đều ít nhất). Khi đi trên một tuyến đường phố, Tuấn tốn chi phí $B$, Mai tốn chi phí $E$, nếu cả hai cùng đi chung trên một tuyến đường phố thì tốn chi phí $P$. Nếu $P$ nhỏ, giải pháp tiết kiệm nhất là Tuấn và Mai cùng đi đến một nút giao thông gặp nhau, sau đó cả hai cùng đi chung cho đến hết quãng đường tới trường. Tuy nhiên, nếu $P$ lớn, việc đi riêng lẻ đến trường vẫn có thể là phương án hợp lý nhất.

Cho biết sơ đồ giao thông của thành phố gồm $N$ nút giao thông được đánh số từ $1$ đến $N$ $(N \geq 3)$ và $M$ tuyến đường phố hai chiều (mỗi đường phố nối 2 nút giao thông). Vị trí của nhà Mai và Tuấn cũng như trường của hai bạn đều nằm ở các nút giao thông. Nhà Tuấn ở nút giao thông $1$, nhà Mai ở nút giao thông $2$, trường của hai bạn ở nút giao thông $N$.

Yêu cầu: Cho $B, E, P$ và sơ đồ giao thông của thành phố, hãy tính chi phí tối thiểu để Tuấn và Mai đến được trường.

Dữ liệu

• Dòng đầu chứa các số nguyên $B, E, P, N, M$ $(1 \leq B, E, P, N, M \leq 40000)$ như mô tả ở trên.
• Trong $M$ dòng tiếp theo, mỗi dòng chứa $2$ số nguyên $x$ và $y$ biểu thị một tuyến đường phố nối nút giao thông $x$ và nút giao thông $y$ $(1 \leq x, y \leq N)$. Các số trên cùng một dòng cách nhau bởi dấu cách. Dữ liệu luôn đảm bảo có đường đi từ nút giao thông $1$ đến nút giao thông $N$ và từ nút giao thông $2$ đến nút giao thông $N$.

Kết quả ra

• Một số nguyên duy nhất là chi phí tối thiểu để Tuấn và Mai đến được trường.

  Ví dụ

Dữ liệu

4 4 5 8 8
1 4
2 3
3 4
4 7
4 5
5 6
6 8
7 8

Kết quả

22

Giải thích

Tuấn đi từ $1 \rightarrow 4$. Mai đi từ $2 \rightarrow 3 \rightarrow 4$. Sau đó cả hai cùng đi chung từ $4 \rightarrow 7 \rightarrow 8$. Tổng chi phí: $1 \times 4 + 2 \times 4 + 2 \times 5 = 22$.