#include <bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define ll long long
#define MOD 1e9 + 7
#define ull unsigned long long
#define iloop(a,b) for(ll i = a; i < b; ++i)
#define jloop(a,b) for(ll j = a; j < b; ++j)
using namespace std;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int,int> ii;
#define sz(a) int((a).size())
#define pb push_back
#define all(c) (c).begin(),(c).end()
#define tr(c,i) for(typeof((c).begin() i = (c).begin(); i != (c).end(); i++)
#define present(c,x) ((c).find(x) != (c).end())
#define cpresent(c,x) (find(all(c),x) != (c).end())
#define p(a) cout << a << "\n";
long n;
vector<pair<int,long > > vec[100005];
int mindistance(ll dist[], bool spt[])
{
long min = INT_MAX, min_index;
for(ll v = 0; v <= n; ++v)
{
if(spt[v] == false && dist[v] <= min)
{
min = dist[v];
min_index = v;
}
}
return min_index;
}
void dijkstra(vector<pair<int,long> > *vec, long s)
{
ll dist[n+1];
bool spt[n+1];
for(int i = 0; i <= n; ++i)
{
dist[i] = INT_MAX;
spt[i] = false;
}
dist[s] = 0;
for(int i = 0; i < n; ++i)
{
int u = mindistance(dist, spt);
spt[u] = true;
for(int j = 0; j < vec[u].size(); ++j)
{
if(!spt[vec[u][j].first] && dist[u] != INT_MAX && dist[u]+vec[u][j].second < dist[vec[u][j].first])
{
dist[vec[u][j].first] = dist[u] + vec[u][j].second;
}
}
}
for(int i = 1; i <= n; ++i)
{
printf("%lld ", dist[i]/2);
}
printf("\n");
}
void solve()
{
long k,x,m,s,a,b,c;
int t;
scanf("%d",&t);
while(t--)
{
scanf("%ld %ld %ld %ld %ld",&n,&k,&x,&m,&s);
iloop(1,n+1)
vec[i].clear();
iloop(1,k+1)
{
vec[i].pb(mp(0,x));
vec[0].pb(mp(i,x));
}
iloop(0,m)
{
scanf("%ld %ld %ld",&a,&b,&c);
vec[a].pb(mp(b,2*c));
vec[b].pb(mp(a,2*c));
}
dijkstra(vec, s);
}
}
int main()
{
bool testing = false;
std::ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
if(testing)
{
freopen("test.txt","rt",stdin);
int start = clock();
solve();
int end = clock();
cout << "time: " << (end - start)/(double)(CLOCKS_PER_SEC)*1000 << " milliseconds\n";
}
else
{
solve();
}
}
ICAgICNpbmNsdWRlIDxiaXRzL3N0ZGMrKy5oPgogICAgI2RlZmluZSBwYiBwdXNoX2JhY2sKICAgICNkZWZpbmUgbXAgbWFrZV9wYWlyCiAgICAjZGVmaW5lIGxsIGxvbmcgbG9uZwogICAgI2RlZmluZSBNT0QgMWU5ICsgNwogICAgI2RlZmluZSB1bGwgdW5zaWduZWQgbG9uZyBsb25nCiAgICAjZGVmaW5lIGlsb29wKGEsYikgZm9yKGxsIGkgPSBhOyBpIDwgYjsgKytpKQogICAgI2RlZmluZSBqbG9vcChhLGIpIGZvcihsbCBqID0gYTsgaiA8IGI7ICsraikKICAgIHVzaW5nIG5hbWVzcGFjZSBzdGQ7CiAgICB0eXBlZGVmIHZlY3RvcjxpbnQ+IHZpOyAKICAgIHR5cGVkZWYgdmVjdG9yPHZpPiB2dmk7IAogICAgdHlwZWRlZiBwYWlyPGludCxpbnQ+IGlpOyAKICAgICNkZWZpbmUgc3ooYSkgaW50KChhKS5zaXplKCkpIAogICAgI2RlZmluZSBwYiBwdXNoX2JhY2sgCiAgICAjZGVmaW5lIGFsbChjKSAoYykuYmVnaW4oKSwoYykuZW5kKCkgCiAgICAjZGVmaW5lIHRyKGMsaSkgZm9yKHR5cGVvZigoYykuYmVnaW4oKSBpID0gKGMpLmJlZ2luKCk7IGkgIT0gKGMpLmVuZCgpOyBpKyspIAogICAgI2RlZmluZSBwcmVzZW50KGMseCkgKChjKS5maW5kKHgpICE9IChjKS5lbmQoKSkgCiAgICAjZGVmaW5lIGNwcmVzZW50KGMseCkgKGZpbmQoYWxsKGMpLHgpICE9IChjKS5lbmQoKSkgCiAgICAjZGVmaW5lIHAoYSkgY291dCA8PCBhIDw8ICJcbiI7CiAgICBsb25nIG47CiAgICB2ZWN0b3I8cGFpcjxpbnQsbG9uZyA+ID4gdmVjWzEwMDAwNV07CiAgICBpbnQgbWluZGlzdGFuY2UobGwgZGlzdFtdLCBib29sIHNwdFtdKQogICAgewogICAgICAgIGxvbmcgbWluID0gSU5UX01BWCwgbWluX2luZGV4OwogICAgICAgIGZvcihsbCB2ID0gMDsgdiA8PSBuOyArK3YpCiAgICAgICAgewogICAgICAgICAgICBpZihzcHRbdl0gPT0gZmFsc2UgJiYgZGlzdFt2XSA8PSBtaW4pCiAgICAgICAgICAgIHsKICAgICAgICAgICAgICAgIG1pbiA9IGRpc3Rbdl07CiAgICAgICAgICAgICAgICBtaW5faW5kZXggPSB2OwogICAgICAgICAgICB9CiAgICAgICAgfQogICAgICAgIHJldHVybiBtaW5faW5kZXg7CiAgICB9CiAgICB2b2lkIGRpamtzdHJhKHZlY3RvcjxwYWlyPGludCxsb25nPiA+ICp2ZWMsIGxvbmcgcykKICAgIHsKICAgICAgICBsbCBkaXN0W24rMV07CiAgICAgICAgYm9vbCBzcHRbbisxXTsKICAgICAgICBmb3IoaW50IGkgPSAwOyBpIDw9IG47ICsraSkKICAgICAgICB7CiAgICAgICAgICAgICAgICBkaXN0W2ldID0gSU5UX01BWDsKICAgICAgICAgICAgICAgIHNwdFtpXSA9IGZhbHNlOwogICAgICAgIH0KICAgICAgICBkaXN0W3NdID0gMDsKICAgICAgICBmb3IoaW50IGkgPSAwOyBpIDwgbjsgKytpKQogICAgICAgIHsKICAgICAgICAgICAgaW50IHUgPSBtaW5kaXN0YW5jZShkaXN0LCBzcHQpOwogICAgICAgICAgICBzcHRbdV0gPSB0cnVlOwogICAgICAgICAgICBmb3IoaW50IGogPSAwOyBqIDwgdmVjW3VdLnNpemUoKTsgKytqKQogICAgICAgICAgICB7IAogICAgICAgICAgICAgICAgaWYoIXNwdFt2ZWNbdV1bal0uZmlyc3RdICYmIGRpc3RbdV0gIT0gSU5UX01BWCAmJiBkaXN0W3VdK3ZlY1t1XVtqXS5zZWNvbmQgPCBkaXN0W3ZlY1t1XVtqXS5maXJzdF0pCiAgICAgICAgICAgICAgICB7CiAgICAgICAgICAgICAgICAgICAgZGlzdFt2ZWNbdV1bal0uZmlyc3RdID0gZGlzdFt1XSArIHZlY1t1XVtqXS5zZWNvbmQ7CiAgICAgICAgICAgICAgICB9CiAgICAgICAgICAgIH0KICAgICAgICB9CiAgICAgICAgZm9yKGludCBpID0gMTsgaSA8PSBuOyArK2kpCiAgICAgICAgewogICAgICAgICAgICBwcmludGYoIiVsbGQgIiwgZGlzdFtpXS8yKTsKICAgICAgICB9ICAgCiAgICAgICAgcHJpbnRmKCJcbiIpOwogICAgfQogICAgdm9pZCBzb2x2ZSgpCiAgICB7CiAgICAgICAgbG9uZyBrLHgsbSxzLGEsYixjOwogICAgICAgIGludCB0OwogICAgICAgIHNjYW5mKCIlZCIsJnQpOwogICAgICAgIHdoaWxlKHQtLSkKICAgICAgICB7CiAgICAgICAgICAgIHNjYW5mKCIlbGQgJWxkICVsZCAlbGQgJWxkIiwmbiwmaywmeCwmbSwmcyk7CiAgICAgICAgICAgIGlsb29wKDEsbisxKQogICAgICAgICAgICB2ZWNbaV0uY2xlYXIoKTsKICAgICAgICAgICAgaWxvb3AoMSxrKzEpCiAgICAgICAgICAgIHsKICAgICAgICAgICAgICAgIHZlY1tpXS5wYihtcCgwLHgpKTsKICAgICAgICAgICAgICAgIHZlY1swXS5wYihtcChpLHgpKTsKICAgICAgICAgICAgfQogICAgICAgICAgICBpbG9vcCgwLG0pCiAgICAgICAgICAgIHsKICAgICAgICAgICAgICAgIHNjYW5mKCIlbGQgJWxkICVsZCIsJmEsJmIsJmMpOwogICAgICAgICAgICAgICAgdmVjW2FdLnBiKG1wKGIsMipjKSk7CiAgICAgICAgICAgICAgICB2ZWNbYl0ucGIobXAoYSwyKmMpKTsKICAgICAgICAgICAgfQogICAgICAgICAgICBkaWprc3RyYSh2ZWMsIHMpOwogICAgICAgIH0KICAgIH0KICAgIGludCBtYWluKCkKICAgIHsKICAgICAgICBib29sIHRlc3RpbmcgPSBmYWxzZTsKICAgICAgICBzdGQ6Omlvczo6c3luY193aXRoX3N0ZGlvKGZhbHNlKTsKICAgICAgICBjaW4udGllKE5VTEwpOwogICAgICAgIGNvdXQudGllKE5VTEwpOwogICAgICAgIGlmKHRlc3RpbmcpCiAgICAgICAgewogICAgICAgICAgICBmcmVvcGVuKCJ0ZXN0LnR4dCIsInJ0IixzdGRpbik7CiAgICAgICAgICAgIGludCBzdGFydCA9IGNsb2NrKCk7CiAgICAgICAgICAgIHNvbHZlKCk7CiAgICAgICAgICAgIGludCBlbmQgPSBjbG9jaygpOwogICAgICAgICAgICBjb3V0IDw8ICJ0aW1lOiAiIDw8IChlbmQgLSBzdGFydCkvKGRvdWJsZSkoQ0xPQ0tTX1BFUl9TRUMpKjEwMDAgPDwgIiBtaWxsaXNlY29uZHNcbiI7CiAgICAgICAgfQogICAgICAgIGVsc2UKICAgICAgICB7CiAgICAgICAgICAgIHNvbHZlKCk7CiAgICAgICAgfQogICAgfSA=