#include <iostream> #include <cstdlib> using namespace std; int d (const void* a,const void* b){int* p1=(int*)a;int* p2=(int*)b; return p1[0] - p2[0];}int main(){int a,b,c,e,f,i,j,k,n;cin>>n>>k>>a>>b;k=2*k;int p[k][2]; int* g;int** h=new int*[n+1];int* l=new int[n+1];int* m=new int[n+1];int* o=new int[n+1]; int *q,*r,*s,*t,*u,*v,*w;q=new int[n];u=q;t=u;r=new int[n];v=r;s=v;w;for(i=0;i<k;i+=2) {cin>>p[i][0]>>p[i][1];p[i+1][1]=p[i][0];p[i+1][0]=p[i][1];}qsort(p,k,2*sizeof(int),d);i=j=0; while(i<k){h[p[i][0]]=p[i];l[p[i][0]]=1;j++;while(p[i][0]==p[j][0]&&j<k){l[p[i][0]]++; j++;}i=j;}if(a==b){cout<<a;return 0;}if(a<b){if(h[1]==NULL){cout<<b;return 0;} m[1]=1;for(i=2;i<=n;i++)m[i]=0;e=a;g=h[1];for(i=0;i<l[1];i++){c=g[1];m[c]=1; if(c==n){cout<<a;return 0;}s++;*s=c;g+=2;}while(s!=v){w=t;t=s;s=w;w=u;u=v;v=w;e=e+a;if(e>=b) {cout<<b;return 0;}while(t!=u){f=*t;t--;g=h[f]; for(j=0;j<l[f];j++){c=g[1];if(m[c]==0){if(c==n&&e<b){cout<<e;return 0;}m[c]=1; s++;*s=c;}g+=2;}}}cout<<b;return 0;}else{if(h[1]==NULL){cout<<b;return 0;}m[1]=1; e=b;g=h[1];for(i=2;i<=n;i++){o[i]=0;}for(i=0;i<l[1];i++){c=g[1];o[c]=1;g+=2;}if(!o[n]){cout<<b;return 0;} for(i=2;i<=n;i++){if(o[i]==0){s++;*s=i;m[i]=1;}else m[i]=0;o[i]=0;}while(s!=v){ w=t;t=s;s=w;w=u;u=v;v=w;e=e+b;if(e>=a){cout<<a;return 0;}while(t!=u){f=*t;t--; g=h[f];for(j=0;j<l[f];j++){c=g[1];o[c]=1;g+=2;} if(o[n]==0&&e<a){cout<<e;return 0;}for(i=2;i<=n;i++){if(o[i]==0&&m[i]==0){m[i]=1; s++;*s = i;}o[i]=0;}}}cout<<a;return 0;}}