#include <bits/stdc++.h>
using namespace std;
typedef long long int ii;
typedef pair<ii,ii> pi;
vector<pi> g[100001];
typedef vector<pi>::iterator vit;
bool visited[100001];
ii dis[100001];
void logic(ii s,ii n)
{
ii x,y,i;
for(i=0;i<=100000;i++){
dis[i]=1000000001;
visited[i]=false;
}
dis[s]=0;
multiset<pi> m;
m.insert(make_pair(0,s));
while(!m.empty())
{
pair <ii , ii> p = *m.begin();
x=p.first; y=p.second;
m.erase(m.begin());
if(visited[y])
continue;
visited[y]=true;
for(i=0;i<g[y].size();i++)
{
ii e,w;
e=g[y][i].first;
w=g[y][i].second;
if(dis[e]>w+dis[y])
{
dis[e]=w+dis[y];
m.insert(make_pair(dis[e],e));
}
}
}
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
ii n,m,i,t,j;
cin>>t;
while(t--){
ii k,x,s;
cin>>n>>k>>x>>m>>s;
while(m--)
{
ii a,b,w;
cin>>a>>b>>w;
g[a].push_back(make_pair(b,w));
g[b].push_back(make_pair(a,w));
}
for(i=1;i<k;i++)
{
for(j=i+1;j<=k;j++)
{
g[i].push_back(make_pair(j,x));
g[j].push_back(make_pair(i,x));
}
}
logic(s,n);
for(i=1;i<=n;i++)
cout<<dis[i]<<" ";
cout<<endl;
}
return 0;
}
I2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+CnVzaW5nIG5hbWVzcGFjZSBzdGQ7CnR5cGVkZWYgbG9uZyBsb25nIGludCBpaTsKdHlwZWRlZiBwYWlyPGlpLGlpPiBwaTsKdmVjdG9yPHBpPiBnWzEwMDAwMV07CnR5cGVkZWYgdmVjdG9yPHBpPjo6aXRlcmF0b3Igdml0Owpib29sIHZpc2l0ZWRbMTAwMDAxXTsKaWkgZGlzWzEwMDAwMV07Cgp2b2lkIGxvZ2ljKGlpIHMsaWkgbikKewogICAgaWkgeCx5LGk7CiAgIGZvcihpPTA7aTw9MTAwMDAwO2krKyl7CiAgICBkaXNbaV09MTAwMDAwMDAwMTsKICAgIHZpc2l0ZWRbaV09ZmFsc2U7CiAgIH0KICAgIGRpc1tzXT0wOwogICAgbXVsdGlzZXQ8cGk+IG07CiAgICBtLmluc2VydChtYWtlX3BhaXIoMCxzKSk7CiAgICB3aGlsZSghbS5lbXB0eSgpKQogICAgewogICAgICAgICBwYWlyIDxpaSAsIGlpPiBwID0gKm0uYmVnaW4oKTsKICAgICAgICAgeD1wLmZpcnN0OyB5PXAuc2Vjb25kOwogICAgICAgICBtLmVyYXNlKG0uYmVnaW4oKSk7CiAgICAgICAgIGlmKHZpc2l0ZWRbeV0pCiAgICAgICAgICAgIGNvbnRpbnVlOwogICAgICAgICAgICB2aXNpdGVkW3ldPXRydWU7CiAgICAgICAgZm9yKGk9MDtpPGdbeV0uc2l6ZSgpO2krKykKICAgICAgICB7CiAgICAgICAgICAgIGlpIGUsdzsKICAgICAgICAgICBlPWdbeV1baV0uZmlyc3Q7CiAgICAgICAgICAgdz1nW3ldW2ldLnNlY29uZDsKICAgICAgICAgIGlmKGRpc1tlXT53K2Rpc1t5XSkKICAgICAgICAgIHsKICAgICAgICAgICAgIGRpc1tlXT13K2Rpc1t5XTsKICAgICAgICAgICAgICBtLmluc2VydChtYWtlX3BhaXIoZGlzW2VdLGUpKTsKICAgICAgICAgIH0KICAgICAgICB9CiAgICB9Cn0KaW50IG1haW4oKQp7CiAgICBpb3NfYmFzZTo6c3luY193aXRoX3N0ZGlvKDApOwogICAgY2luLnRpZSgwKTsKICAgIGlpIG4sbSxpLHQsajsKICAgIGNpbj4+dDsKICAgIHdoaWxlKHQtLSl7CiAgaWkgayx4LHM7CiAgICBjaW4+Pm4+Pms+Png+Pm0+PnM7CiAgICB3aGlsZShtLS0pCiAgICB7CiAgICAgICAgaWkgYSxiLHc7CiAgICAgICAgY2luPj5hPj5iPj53OwogICAgICAgIGdbYV0ucHVzaF9iYWNrKG1ha2VfcGFpcihiLHcpKTsKICAgICAgICBnW2JdLnB1c2hfYmFjayhtYWtlX3BhaXIoYSx3KSk7CgogICAgfQogICAgZm9yKGk9MTtpPGs7aSsrKQogICB7CiAgICAgICAgZm9yKGo9aSsxO2o8PWs7aisrKQogICAgICAgIHsKICAgICAgICBnW2ldLnB1c2hfYmFjayhtYWtlX3BhaXIoaix4KSk7CiAgICAgICAgZ1tqXS5wdXNoX2JhY2sobWFrZV9wYWlyKGkseCkpOwogICAgICAgIH0KICAgIH0KICAgICBsb2dpYyhzLG4pOwoKICAgIGZvcihpPTE7aTw9bjtpKyspCiAgICAgICAgY291dDw8ZGlzW2ldPDwiICI7CiAgICBjb3V0PDxlbmRsOwogICAgfQogICAgcmV0dXJuIDA7Cn0K
Mwo1IDQgMTAwIDIgMwoxIDUgNTAKNSAzIDE2MAo1IDQgMTAwIDIgMwoxIDUgNTAKNSAzIDE0MAo4IDMgMTUgNyA1CjMgNCAxMAo0IDUgMjAKNSA2IDEwCjYgMSA3CjMgNyAxMDAwCjcgOCA1MAozIDUgMTAwMDAwMDAwMA==
3
5 4 100 2 3
1 5 50
5 3 160
5 4 100 2 3
1 5 50
5 3 140
8 3 15 7 5
3 4 10
4 5 20
5 6 10
6 1 7
3 7 1000
7 8 50
3 5 1000000000