#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 1 << 17;
const ll inf = (ll)1e18;
int n, k, m, s;
ll dist[N], a[18];
vector<pair<int,int>> V[N];
vector<int> bits[18];
bool done[N];

struct Node{
  int id, e;
  ll d;
  Node(){}
  Node(int id, int e, ll d):id(id),e(e),d(d){}
  bool operator < (const Node &A)const{
    return d > A.d;
  }
};


int main(){
  scanf("%d %d %d", &k, &m, &s);
  n = 1 << k;
  for(int i=1; i<=k; ++i) scanf("%lld", a+i);

  int x, y, z;
  while(m--){
    scanf("%d %d %d", &x, &y, &z);
    V[x].emplace_back(y, z);
    V[y].emplace_back(x, z);
  }

  for(int i=1; i<n; ++i){
    bits[__builtin_popcount(i)].push_back(i);
  }

  for(;;){
    bool flag = 0;
    for(int i=1; i<=k; ++i){
      for(int j=i; j<=k; ++j){
        for(int x=0; x<=min(i, j); ++x){
          if(i + j - x <= k){
            ll tmp = a[i] + a[j];
            if(tmp < a[i+j-x]){
              a[i+j-x] = tmp;
              flag = 1;
            }
          }
        }
      }
    }
    if(!flag) break;
  }

  for(int i=0; i<n; ++i)  dist[i] = inf;
  dist[s] = 0;
  priority_queue<Node> Q;
  Q.emplace(s, 0, 0);

  while(!Q.empty()){
    auto nd = Q.top(); Q.pop();
    vector<int> cur;
    if(nd.e > 0){
      for(int v : bits[nd.e]){
        int to = nd.id ^ v;
        if(nd.d < dist[to]){
          dist[to] = nd.d;
          cur.push_back(to);
        }
      }
    } else {
      if(done[nd.id]) continue;
      cur.push_back(nd.id);
    }

    for(int x : cur){
      done[x] = 1;
      for(auto [to, z] : V[x]){
        if(nd.d + z < dist[to]){
          dist[to] = nd.d + z;
          Q.emplace(to, 0, dist[to]);
        }
      }
    }

    if(!nd.e){
      for(int i=1; i<=k; ++i){
        Q.emplace(nd.id, i, nd.d + a[i]);
      }
    }
  }

  for(int i=0; i<n; ++i){
    printf("%lld%c", dist[i], " \n"[i == n - 1]);
  }


  return 0;
}