#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N=4e5+5,inf=1e18;
int k,m,s,w[N],n,son[N][2],sm[N],dy[N],d[N],mk[N];
vector<pair<int,int> >p[N];
struct node{
	int bh,op,x,sm;
	friend bool operator<(node a,node b){
		return a.sm>b.sm;
	}
};
priority_queue<node>q;
void upset(int x){
	sm[x]=max(sm[x<<1],sm[x<<1|1]);
}
void upt(int x){
	if(x==1)return;
	upset(x>>1);
	upt(x>>1);
}
void reset(int x,int cs,int nw){
	if(cs==0){
		dy[nw]=x;
		sm[x]=inf;
		return;
	}
	son[x][0]=x<<1;
	son[x][1]=x<<1|1;
	reset(x<<1,cs-1,nw<<1);
	reset(x<<1|1,cs-1,nw<<1|1);
	upset(x);
}
void solve(int x,int y,int k,int cs,int nw,int val){
	if(sm[x]<=val)return;
	if(cs<k)return;
	if(cs==0){
		d[nw]=val;
		sm[x]=val;
		q.push({nw,0,0,d[nw]});
		upt(x);
		return;
	}
	int c=y>>cs-1&1;
	solve(son[x][c],y,k,cs-1,nw<<1|c,val);
	solve(son[x][c^1],y,k-1,cs-1,nw<<1|(c^1),val);
}
signed main(){
	cin>>k>>m>>s;
	n=(1<<k)-1;
	reset(1,k,0);
	for(int i=1;i<=k;i++)cin>>w[i];
	for(int i=1;i<=m;i++){
		int x,y,z;
		cin>>x>>y>>z;
		p[x].push_back({y,z});
		p[y].push_back({x,z});
	}
	q.push({s,0,0,0});
	memset(d,0x3f,sizeof(d));
	d[s]=0;
	sm[dy[s]]=0;
	upt(dy[s]);
	while(q.size()){
		int x=q.top().bh,op=q.top().op,y=q.top().x;
		q.pop();
		//cout<<x<<" "<<op<<" "<<y<<endl;
		if(op==0){
			if(mk[x])continue;
			mk[x]=1;
			for(int i=1;i<=k;i++){
				q.push({x,1,i,d[x]+w[i]});
			}
			for(auto [c,sms]:p[x]){
				if(d[x]+sms<d[c]){
					d[c]=d[x]+sms;
					sm[dy[c]]=d[c];
					upt(dy[c]);
					q.push({c,0,0,d[c]});
				}
			}
		}else{
			solve(1,x,y,k,0,d[x]+w[y]);
		}
	}
	for(int i=0;i<=n;i++)cout<<d[i]<<" ";
}