Piggy Back

Bessie and her sister Elsie graze in different fields during the day, and in the evening both of them want to walk back to the barn to rest. The two cows want the total energy they spend on the walk to be as small as possible.

Bessie spends $B$ units of energy every time she walks to an adjacent field, and Elsie spends $E$ units of energy for the same move. When both cows stand in the same field, Bessie can carry Elsie on her shoulders, and then the two of them move together to an adjacent field for a combined $P$ units of energy. $P$ can be much smaller than $B + E$. In that case the cheapest plan has them meet in a common field first and travel piggyback for the rest of the way. If $P$ is large, walking separately the whole way can still cost less.

Given $B$, $E$, $P$ and the layout of the farm, compute the minimum total energy Bessie and Elsie need to spend to reach the barn.

The first line contains the positive integers $B$, $E$, $P$, $N$, $M$, separated by spaces. All five values are at most 40000. $N$ is the number of fields, the fields are numbered 1 to $N$, and $N \ge 3$. $M$ is the number of connections between fields. Bessie starts in field 1, Elsie starts in field 2, and the barn is in field $N$.

Each of the next $M$ lines contains the indices of two different fields and describes one connection between them. A connection can be walked in both directions. It is always possible to travel from field 1 to field $N$, and from field 2 to field $N$, along connections.

Print one integer, the minimum total energy that Bessie and Elsie spend together to reach the barn.