#pragma GCC optimize("Ofast")
#pragma GCC target("popcnt,avx2,abm")
#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> s[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 < 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);
      }
    }
  }

  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) {
        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]) {
            pq.emplace(-(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;
}

In file included from /usr/include/c++/13/string:43,
                 from /usr/include/c++/13/bitset:52,
                 from /usr/include/x86_64-linux-gnu/c++/13/bits/stdc++.h:52,
                 from /usr/include/x86_64-linux-gnu/c++/13/bits/extc++.h:32,
                 from answer.code:3:
/usr/include/c++/13/bits/allocator.h: In destructor ‘constexpr std::_Vector_base<int, std::allocator<int> >::_Vector_impl::~_Vector_impl()’:
/usr/include/c++/13/bits/allocator.h:184:7: error: inlining failed in call to ‘always_inline’ ‘constexpr std::allocator< <template-parameter-1-1> >::~allocator() noexcept [with _Tp = int]’: target specific option mismatch
  184 |       ~allocator() _GLIBCXX_NOTHROW { }
      |       ^
In file included from /usr/include/c++/13/vector:66,
                 from /usr/include/c++/13/functional:64,
                 from /usr/include/x86_64-linux-gnu/c++/13/bits/stdc++.h:53:
/usr/include/c++/13/bits/stl_vector.h:133:14: note: called from here
  133 |       struct _Vector_impl
      |              ^~~~~~~~~~~~