// Problem: P9377 [THUPC 2023 决赛] 百合
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P9377
// Memory Limit: 512 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
#define pb emplace_back
#define fst first
#define scd second
#define mkp make_pair
#define mems(a, x) memset((a), (x), sizeof(a))

using namespace std;
typedef long long ll;
typedef double db;
typedef unsigned long long ull;
typedef long double ldb;
typedef pair<ll, ll> pii;

const int maxn = (1 << 17) + 50;

ll n, m, K, S, f[maxn], g[maxn][18], a[maxn];
bool vis[maxn];
vector<pii> G[maxn];

struct node {
	ll u, d;
	node(ll a = 0, ll b = 0) : u(a), d(b) {}
};

inline bool operator < (const node &a, const node &b) {
	return a.d > b.d;
}

inline void dij() {
	priority_queue<node> pq;
	for (int i = 0; i < n; ++i) {
		pq.emplace(i, f[i]);
		vis[i] = 0;
	}
	while (pq.size()) {
		int u = pq.top().u;
		pq.pop();
		if (vis[u]) {
			continue;
		}
		vis[u] = 1;
		for (pii p : G[u]) {
			ll v = p.fst, d = p.scd;
			if (f[v] > f[u] + d) {
				f[v] = f[u] + d;
				if (!vis[v]) {
					pq.emplace(v, f[v]);
				}
			}
		}
	}
}

void solve() {
	scanf("%lld%lld%lld", &K, &m, &S);
	n = (1 << K);
	for (int i = 1; i <= K; ++i) {
		scanf("%lld", &a[i]);
	}
	while (m--) {
		ll u, v, d;
		scanf("%lld%lld%lld", &u, &v, &d);
		G[u].pb(v, d);
		G[v].pb(u, d);
	}
	for (int i = 0; i < n; ++i) {
		G[i].pb(n - 1 - i, a[K]);
		G[n - 1 - i].pb(i, a[K]);
	}
	mems(f, 0x3f);
	f[S] = 0;
	for (int _ = 0; _ < K; ++_) {
		dij();
		mems(g, 0x3f);
		for (int i = 0; i < n; ++i) {
			g[i][0] = f[i];
		}
		for (int i = 0; i < K; ++i) {
			for (int j = 0; j < n; ++j) {
				if (j & (1 << i)) {
					int k = j ^ (1 << i);
					for (int l = K - 1; l; --l) {
						g[j][l] = min(g[j][l], g[k][l - 1]);
						g[k][l] = min(g[k][l], g[j][l - 1]);
					}
				}
			}
		}
		for (int i = 0; i < n; ++i) {
			for (int j = 1; j < K; ++j) {
				f[i] = min(f[i], g[i][j] + a[j]);
			}
		}
	}
	dij();
	for (int i = 0; i < n; ++i) {
		printf("%lld ", f[i]);
	}
	putchar('\n');
}

int main() {
	int T = 1;
	// scanf("%d", &T);
	while (T--) {
		solve();
	}
	return 0;
}