#pragma GCC optimize("Ofast")
#pragma GCC target("popcnt")
#include <bits/extc++.h>
#include <bits/stdc++.h>
using namespace std;

constexpr int B = 6;
constexpr int K = 17;
constexpr int C = K - B;
constexpr int B2 = 1 << B;
constexpr int C2 = 1 << C;
constexpr int N = 1 << K;

constexpr int64_t INF = 1LL << 60;

vector<int> vv[C2];
bool vis[B2][C2][K + 1];

int a[K + 1];

vector<pair<int, int>> g[N];

int64_t d[N];

int main() {
  cin.tie(nullptr)->sync_with_stdio(false);
  int k, m, S;
  cin >> k >> m >> S;
  for (int i = 1; i <= k; ++i)
    cin >> a[i];
  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);
  }
  
  const int n = 1 << k;
  fill_n(d, n, INF);

  for (int i = 0; i < C2; ++i)
    vv[popcount(uint32_t(i))].push_back(i);

  priority_queue<pair<int64_t, int>> pq;
  pq.emplace(d[S] = 0, S);
  while (not pq.empty()) {
    auto [l, u] = pq.top();
    pq.pop();
    if (l != -d[u])
      continue;

    for (auto [v, w] : g[u]) {
      if (d[u] + w < d[v]) {
        pq.emplace(-(d[v] = d[u] + w), v);
      }
    }

    const int j = u & (C2 - 1);
    for (int i = 0; i < B2; ++i) {
      for (int c = 0; c <= C; ++c) {
        const int ll = popcount(uint32_t(i) ^ uint32_t(u >> C)) + c;
        if (vis[i][j][ll])
          continue;
        int cost = a[ll];
        for (int vp : vv[c]) {
          const int v = (i << C) + (j ^ vp);
          if (v >= n)
            continue;
          if (d[u] + cost < d[v]) {
            pq.emplace(-(d[v] = d[u] + cost), v);
          }
        }
        vis[i][j][ll] = true;
      }
    }
  }

  for (int i = 0; i < n; ++i)
    cout << d[i] << " ";
  return 0;
}