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

template <typename T>
using MaxHeap = __gnu_pbds::priority_queue<T, greater<T>>;

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> s[B2][C2][K + 1];

int a[K + 1];

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

int64_t d[N];

int state[N];
MaxHeap<pair<int64_t, int>>::point_iterator pqit[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 < B2; ++i) {
    for (int j = 0; j < C2; ++j) {
      for (int jj = 0; jj < C2; ++jj) {
        int c = popcount(uint32_t(j) ^ uint32_t(jj));
        s[i][j][c].push_back((i << C) + jj);
      }
    }
  }

  MaxHeap<pair<int64_t, int>> pq;
  pq.push({d[S] = 0, S});
  state[S] = 2;
  while (not pq.empty()) {
    auto [l, u] = pq.top();
    pq.pop();
    state[u] = 2;

    for (auto [v, w] : g[u]) {
      if (d[u] + w < d[v]) {
        if (state[v] == 0) {
          state[v] = 1;
          pqit[v] = pq.push({-(d[v] = d[u] + w), v});
        } else if (state[v] == 1) {
          pq.modify(pqit[v], {-(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) {
        int cost = a[popcount(uint32_t(i) ^ uint32_t(u >> C)) + c];
        for (int v : s[i][j][c]) {
          if (d[u] + cost < d[v]) {
            if (state[v] == 0) {
              state[v] = 1;
              pqit[v] = pq.push({-(d[v] = d[u] + cost), v});
            } else if (state[v] == 1) {
              pq.modify(pqit[v], {-(d[v] = d[u] + cost), v});
            }
          }
        }
        s[i][j][c].clear();
      }
    }
  }

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