#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 1 << 17;
const int M = 18;
const ll inf = (ll)1e18;

int K, m, s, n, a[M];
vector<pair<int,int>> V[N];
ll dist[N];
int lst[N][M];

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

void dfs(int id, int x, int y, ll d){
  if(d + a[y] < dist[id]){
    dist[id] = d + a[y];
    Q.emplace(id, dist[id]);
  }
  if(x + 1 < lst[id][y]){
    dfs(id, x + 1, y, d);
    dfs(id^(1<<x), x+1, y+1, d);
    lst[id][y] = x;
  }
}

int main(){
  int x, y, z;
  scanf("%d %d %d", &K, &m, &s);
  for(int i=1; i<=K; ++i) scanf("%d", a+i);
  n = 1 << K;
  while(m--){
    scanf("%d %d %d", &x, &y, &z);
    V[x].emplace_back(y, z);
    V[y].emplace_back(x, z);
  }
  for(int i=0; i<n; ++i){
    dist[i] = inf;
    for(int j=0; j<=K; ++j){
      lst[i][j] = K + 1;
    }
  }
  dist[s] = 0;
  Q.emplace(s, 0);
  while(!Q.empty()){
    auto nd = Q.top(); Q.pop();
    if(nd.d > dist[nd.id])  continue;

    dfs(nd.id, 0, 0, nd.d);

    for(auto [to, z] : V[nd.id]){
      if(nd.d + z < dist[to]){
        dist[to] = nd.d + z;
        Q.emplace(to, dist[to]);
      }
    }
  }

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