#include <concepts> #include <iostream> #include <queue> #include <tuple> #include <utility> #include <vector> using namespace std; using i64 = long long; constexpr i64 INF = 0x3f3f3f3f3f3f3f3f; struct IO { static constexpr int MAX_LEN = 1 << 20; char buf[MAX_LEN], *p1, *p2; char pbuf[MAX_LEN], *pp; IO() : p1(buf) , p2(buf) , pp(pbuf) { } ~IO() { fwrite(pbuf, 1, pp - pbuf, stdout); } char getch() { if (p1 == p2) p2 = (p1 = buf) + fread(buf, 1, MAX_LEN, stdin); return p1 == p2 ? ' ' : *p1++; } IO& read(integral auto& x) { int sgn = 1; char ch = getch(); x = 0; for (; !isdigit(ch); ch = getch()) { if (ch == '-') sgn *= -1; } for (; isdigit(ch); ch = getch()) x = x * 10 + (ch - '0'); x *= sgn; return *this; } IO& read(char* s) { char ch = getch(); for (; isspace(ch); ch = getch()) ; for (; !isspace(ch); ch = getch()) *s++ = ch; *s = 0; return *this; } IO& read(char& c) { for (c = getch(); isspace(c); c = getch()) ; return *this; } void push(const char& c) { if (pp - pbuf == MAX_LEN) { fwrite(pbuf, 1, MAX_LEN, stdout); pp = pbuf; } *pp++ = c; } IO& write(integral auto x) { if (x < 0) { x = -x; push('-'); } else if (x == 0) { push('0'); return *this; } int top = 0, ch[40]; do { ch[top++] = x % 10; x /= 10; } while (x > 0); while (top > 0) push('0' + ch[--top]); return *this; } IO& write(integral auto x, char lst) { write(x); push(lst); return *this; } } io; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); int k, m, s; io.read(k); io.read(m); io.read(s); vector<int> a(k + 1); for (int i = 1; i <= k; ++i) io.read(a[i]); int n = 1 << k; vector<vector<pair<int, int>>> graph(n); for (int i = 0; i < m; ++i) { int u, v, c; io.read(u); io.read(v); io.read(c); graph[u].emplace_back(v, c); graph[v].emplace_back(u, c); } priority_queue<pair<i64, int>> nodes1; vector vis(n, vector(k + 1, vector(k + 1, false))); vector dist(n, INF); dist[s] = 0; nodes1.emplace(0, s); while (!nodes1.empty()) { auto [dis, cur] = nodes1.top(); nodes1.pop(); dis = -dis; if (dis != dist[cur]) continue; for (auto [nxt, cost] : graph[cur]) { if (dist[nxt] > dist[cur] + cost) { dist[nxt] = dist[cur] + cost; nodes1.emplace(-dist[nxt], nxt); } } vector<tuple<int, int, int>> nodes2; nodes2.emplace_back(cur, 0, 0); while (!nodes2.empty()) { auto [u, i, j] = nodes2.back(); nodes2.pop_back(); if (vis[u][i][j]) continue; vis[u][i][j] = true; if (i == k && dist[u] > dis + a[j]) { dist[u] = dis + a[j]; nodes1.emplace(-dist[u], u); } else if (i < k) { nodes2.emplace_back(u, i + 1, j); nodes2.emplace_back(u ^ (1 << i), i + 1, j + 1); } } } for (int i = 0; i < n; ++i) io.write(dist[i], ' '); return 0; }