#include <bits/stdc++.h>
#ifndef SKY
#include "highway.h"
#endif // SKY
using namespace std;
#define N 200010
#define ll long long
#define fs first
#define sc second
#define ii pair<int,int>
#define pb push_back
int times,root,ktr[N],cha[N][21],n,m,depth[N],par_id[N];
ll A,B;
ii canh[N],cnt[N];
vector<ii>g[N],ke[N];
queue<int>dq;
#ifdef SKY
int S_ans,T_ans;
void answer(int s,int t)
{
cout<<s<<" "<<t<<endl;
}
ll dis[55][55];
ll ask(vector<int>w)
{
memset(dis,0x3f3f,sizeof(dis));
for(int i=0;i<m;i++)
dis[canh[i].fs][canh[i].sc]=dis[canh[i].sc][canh[i].fs]=(w[i]==0 ? A : B);
for(int k=0;k<n;k++)
for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]);
return dis[S_ans][T_ans];
}
#endif // SKY
int query;
ll my_ask(vector<int>w)
{
// assert(w.size()==m);
//assert(++query<=50);
return ask(w);
}
ll get_dinh(vector<int>s)
{
vector<int>w(m,0);
for(auto u:s)
{
for(auto v:ke[u])
w[v.sc]=1;
}
return my_ask(w);
}
void DFS(int u,int p)
{
cnt[u].fs=++times;
for(auto v:g[u])
if(v.fs!=p)
{
par_id[v.fs]=v.sc;
depth[v.fs]=depth[u]+1;
cha[v.fs][0]=u;
DFS(v.fs,u);
}
cnt[u].sc=times;
}
bool tren(int u,int v)
{
return (cnt[u].fs<=cnt[v].fs&&cnt[u].sc>=cnt[v].sc);
}
bool SS(const int&u,const int&v)
{
return depth[u]<depth[v];
}
ll get(vector<int>s,int u,int sau)
{
vector<int>w(m,1);
for(auto u:s)
w[par_id[u]]=0;
while(depth[u]>=sau)
{
w[par_id[u]]=0;
u=cha[u][0];
}
return my_ask(w);
}
void find_pair(int cc, vector<int> canh_fs, vector<int> canh_sc, int AAA, int BBB)
{
n=cc;
m=canh_fs.size();
A=AAA;
B=BBB;
for(int i=0;i<m;i++)
{
canh[i]={canh_fs[i],canh_sc[i]};
ke[canh[i].fs].pb({canh[i].sc,i});
ke[canh[i].sc].pb({canh[i].fs,i});
}
ll val=my_ask(vector<int>(m,0));
vector<int>s;
for(int i=0;i<n;i++)
s.pb(i);
// cout<<val<<endl;
while(s.size()>1)
{
vector<int>L,R;
for(int i=0;i<s.size();i++)
if(i*2<s.size())
L.pb(s[i]);
else R.pb(s[i]);
if(get_dinh(L)!=val)
s=L;
else s=R;
}
assert(get_dinh(s)!=val);
root=s[0];
ktr[root]=1;
dq.push(root);
while(!dq.empty())
{
int u=dq.front();
dq.pop();
for(auto v:ke[u])
if(ktr[v.fs]==0)
{
ktr[v.fs]=1;
g[u].pb(v);
g[v.fs].pb({u,v.sc});
// cout<<u<<" "<<v.fs<<endl;
dq.push(v.fs);
}
}
//cout<<root<<endl;
val=val/A*B;
DFS(root,-1);
s.clear();
for(int i=0;i<n;i++)
s.pb(i);
sort(s.begin(),s.end(),SS);
int l=1,r=n-1,S=-1;
// for(int i=0;i<n;i++)cout<<s[i]<<" ";cout<<endl;
//vector<int>thu(m,1);thu[9]=0;cout<<my_ask(thu)<<" "<<val<<endl;
while(l<=r)
{
int mid=(l+r)/2;
vector<int>hoi(m,1);
for(int i=mid;i<n;i++)
hoi[par_id[s[i]]]=0;
if(my_ask(hoi)!=val)
{
S=s[mid];
l=mid+1;
// cout<<s[mid]<<endl;
}else
r=mid-1;
}
if(val/B==depth[S])
{
answer(S,root);
return;
}
int sau=val/B-depth[S];
s.clear();
for(int i=0;i<n;i++)
if(depth[i]==sau&&!tren(i,S))
s.pb(i);
while(s.size()>1)
{
vector<int>L,R;
for(int i=0;i<s.size();i++)
if(i*2<s.size())
L.pb(s[i]);
else R.pb(s[i]);
if(get(L,S,sau)!=val-1ll*(B-A)*(depth[S]-sau+1))
s=L;
else s=R;
}
answer(S,s[0]);
}
#ifdef SKY
int main()
{
freopen("A.inp","r",stdin);
freopen("A.out","w",stdout);
ios::sync_with_stdio(0);
cin.tie(NULL);
cout.tie(NULL);
srand(time(0));
int n,m,A,B;
map<int,int>mp[110];
cin>>n>>m>>S_ans>>T_ans>>A>>B;
vector<int>u(m),v(m);
//for(int i=0;i<m;i++)
// cin>>u[i]>>v[i];
for(int i=0;i<n-1;i++)
{
u[i]=i+1;
v[i]=rand()%(i+1);
mp[min(u[i],v[i])][max(u[i],v[i])]++;
}
for(int i=n-1;i<m;i++)
{
u[i]=rand()%n;
do{
v[i]=rand()%n;
}while(u[i]==v[i]||mp[min(u[i],v[i])][max(u[i],v[i])]!=0);
assert(u[i]!=v[i]);
mp[min(u[i],v[i])][max(u[i],v[i])]++;
}
for(int i=0;i<m;i++)cout<<u[i]<<" "<<v[i]<<endl;
find_pair(n,u,v,A,B);
return 0;
}
#endif
