#include <bits/extc++.h>
#include <bits/stdc++.h>
using namespace std;

int main() {
	cin.tie(nullptr)->sync_with_stdio(false);
	int k, m, s;
	cin >> k >> m >> s;
	vector<int> a(k + 1);
	for (int i = 1; i <= k; ++i)
		cin >> a[i];
	const int n = 1 << k;
	vector<vector<pair<int, int>>> g(n + n * k * k);
	for (int i = 0; i < m; ++i) {
		int u, v, w;
		cin >> u >> v >> w;
		g[u].emplace_back(v, w);
		g[v].emplace_back(u, w);
	}
	auto enc = [&](int x, int i, int j) {
		return n + (x * k + i) * k + j;
	};
	for (int u = 0; u < n; ++u) {
		g[u].emplace_back(enc(u, 0, 0), 0);
		g[u].emplace_back(enc(u ^ 1, 0, 1), 0);
		for (int i = 0; i < k; ++i) {
			for (int j = 0; j <= i; ++j) {
				if (i + 1 == k) {
					g[enc(u, i, j)].emplace_back(u, a[j]);
					g[enc(u, i, j)].emplace_back(u ^ (1 << i), a[j + 1]);
				} else {
					g[enc(u, i, j)].emplace_back(enc(u, i + 1, j), 0);
					g[enc(u, i, j)].emplace_back(enc(u ^ (1 << i), i + 1, j + 1), 0);
				}
			}
		}
	}
	priority_queue<pair<int64_t, int>> pq;
	vector<int64_t> d(g.size(), 1LL << 60);
	pq.emplace(d[s] = 0, s);
	while (not pq.empty()) {
		auto [l, u] = pq.top();
		pq.pop();
		if (l != -d[u])
			continue;

		queue<int> bfs;
		bfs.push(u);
		while (not bfs.empty()) {
			int x = bfs.front();
			bfs.pop();
			for (auto [y, w] : g[x]) {
				if (d[x] + w >= d[y])
					continue;
				if (w == 0) {
					d[y] = d[x];
					bfs.push(y);
				} else {
					pq.emplace(-(d[y] = d[x] + w), y);
				}
			}
		}
	}
	for (int i = 0; i < n; ++i)
		cout << d[i] << " \n"[i + 1 == n];
	return 0;
}