#include <bits/stdc++.h>

using namespace std;

#define FOR(i, a, b) for(int i = (a); i < (b); i++)
#define RFOR(i, a, b) for(int i = (a) - 1; i >= (b); i--)
#define SZ(a) int(a.size())
#define ALL(a) a.begin(), a.end()
#define PB push_back
#define MP make_pair
#define F first
#define S second

typedef long long LL;
typedef vector<int> VI;
typedef pair<int, int> PII;
typedef double db;

const int mod1 = 19880830;
const int mod2 = 754974721;

int add(int a, int b, int mod)
{
	return a + b < mod ? a + b : a + b - mod;
}
int sub(int a, int b, int mod)
{
	return a - b >= 0 ? a - b : a - b + mod;
}
int mult(int a, int b, int mod)
{
	return (LL)a * b % mod;
}

const int INF = 1e9 + 47; 
const int N = 100'447;
vector<PII> g[N];
int n, m, s, t, Q;
int d[2][N];
int cnt1[2][N];
int cnt2[2][N];
int l[N], c[N];

void dijk(int v, int tt)
{
	d[tt][v] = 0;
	cnt1[tt][v] = 1;
	cnt2[tt][v] = 1;
	set<PII> q;
	q.insert({d[tt][v], v});
	while (!q.empty())
	{
		int u = q.begin()->S;
		q.erase(q.begin());
		for (auto [to, w] : g[u])
		{
			if (d[tt][to] > d[tt][u] + w)
			{
				q.erase({d[tt][to], to});
				d[tt][to] = d[tt][u] + w;
				cnt1[tt][to] = 0;
				cnt2[tt][to] = 0;
				q.insert({d[tt][to], to});
			}
			if (d[tt][to] == d[tt][u] + w)
			{
				cnt1[tt][to] = add(cnt1[tt][to], cnt1[tt][u], mod1);
				cnt2[tt][to] = add(cnt2[tt][to], cnt2[tt][u], mod2);
			}
		}
	}
}

map<int, int> m1, m2;

void erase(int u, int v, int w)
{
	int d1 = d[0][u] + w + d[1][v];
	m1[d1] = sub(m1[d1], mult(cnt1[0][u], cnt1[1][v], mod1), mod1);
	if (m1[d1] == 0)
		m1.erase(d1);
	m2[d1] = sub(m2[d1], mult(cnt2[0][u], cnt2[1][v], mod2), mod2);
	if (m2[d1] == 0)
		m2.erase(d1);
}

void insert(int u, int v, int w)
{	
	int d1 = d[0][u] + w + d[1][v];
	m1[d1] = add(m1[d1], mult(cnt1[0][u], cnt1[1][v], mod1), mod1);
	m2[d1] = add(m2[d1], mult(cnt2[0][u], cnt2[1][v], mod2), mod2);
}


void solve()
{
	FOR (tt, 0, 2)
	{
		FOR (i, 0, n)
		{
			d[tt][i] = INF;
			cnt1[tt][i] = 0;
			cnt2[tt][i] = 0;
		}
	}
	s--, t--;
	FOR (i, 0, m)
	{
		int u, v, w;
		cin >> u >> v >> w;
		u--, v--;
		g[u].PB({v, w});
		g[v].PB({u, w});
	}
	dijk(s, 0);
	dijk(t, 1);
	
	VI used(n, 0);
	VI idx(n);
	iota(ALL(idx), 0);
	sort(ALL(idx), [&](int i, int j)
	{
		return d[0][i] < d[0][j];
	});
	for (auto v : idx)
	{
		if (v == t)
		{
			l[v] = c[v] = 0;
			used[v] = true;
			break;
		}
		for (auto [to, w] : g[v])
		{
			if (used[to])
				erase(to, v, w);
		}
		used[v] = true;
		if (m1.empty() && m2.empty())
			l[v] = 0, c[v] = 0;
		else
		{
			LL mn = min(m1.empty() ? INF : m1.begin()->F, m2.empty() ? INF : m2.begin()->F);
			if (mn >= INF)
				l[v] = c[v] = 0;
			else
			{
				l[v] = mn;
				c[v] = m1[mn];
			}
		}
		for (auto [to, w] : g[v])
		{
			if (!used[to])
				insert(v, to, w);
		}
	}
	
	FOR (i, 0, n)
	{
		if (!used[i])
		{
			l[i] = d[0][t];
			c[i] = cnt1[0][t];
		}
	}
	//cerr << '\n';
	//FOR (i, 0, n)
	//	cerr << i << ' ' << l[i] << ' ' << c[i] << '\n';
	//cerr << "\n\n";
	FOR (i, 0, Q)
	{
		int x;
		cin >> x;
		x %= mod1;
		int pw = 1;
		int ans = 0;
		FOR (v, 0, n)
		{
			ans = add(ans, mult(l[v], pw, mod1), mod1);
			pw = mult(pw, x, mod1);
			ans = add(ans, mult(c[v], pw, mod1), mod1);
			pw = mult(pw, x, mod1);
		}
		cout << ' ' << ans;
	}
	cout << '\n';
	FOR (i, 0, n)
	{
		g[i].clear();
		l[i] = 0;
		c[i] = 0;
	}
	m1.clear();
	m2.clear();
}

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	for (int tc = 1; ; tc++)
	{
		cin >> n >> m >> s >> t >> Q;
		if (n == 0)
			break;
		cout << "Case " << tc << ":";
		solve();
		cout << '\n';
	}
	return 0;
}