#include<queue>
#include<cstdio>
#include<cstring>
#include<iostream>
#define db double
#define pc putchar
#define ll long long
#define Tp template<typename _T>
Tp _T mabs(_T a){ return a<0?-a:a; }
Tp _T mmax(_T a,_T b){ return a<b?b:a; }
Tp _T mmin(_T a,_T b){ return a<b?a:b; }
Tp void mswap(_T &a,_T &b){ _T t=a; a=b; b=t; return; }
using namespace std;
struct IO{
	char buf[1<<21],*p1,*p2;
	char gc(){ return p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++; }
	IO & operator >> (char &x){ x=gc(); while(x=='\r'||x=='\n'||x==' ') x=gc(); return *this; }
	Tp IO & operator >> (_T &x){
		x=0; char c=gc(); bool f=0; while(c<'0'||c>'9'){ if(c=='-') f^=1; c=gc(); }
		while('0'<=c&&c<='9') x=(x<<1)+(x<<3)+(c^48),c=gc(); f?x=-x:0; return *this;
	}
	int st[39],top;
	IO & operator << (char x) { pc(x); return *this; }
	Tp IO & operator << (_T x){
		if(x<0) x=-x,pc('-'); if(x==0){ pc('0'); return *this; }
		top=0; while(x) st[++top]=x%10,x/=10;
		while(top--) pc(st[top+1]+48); return *this;
	}
}fin;
#define maxn 200039
#define maxm 400039
int n,m,s,k,u,v,w,a[39],head[maxn],to[maxm],nex[maxm],c[maxm],kkk;
#define add(x,y,z) nex[++kkk]=head[x]; head[x]=kkk; to[kkk]=y; c[kkk]=z
ll f[maxn][19],dis[maxn]; int vis[maxn];
struct JTZ{
	int num; ll dis;
	bool operator < (const JTZ &x) const {
		return this->dis > x.dis;
	}
};
priority_queue<JTZ> q,E;
void Dij(){
	int i; JTZ cur; for(i=0;i<n;i++) q.push((JTZ){i,dis[i]}),vis[i]=0;
	while(!q.empty()){
		cur=q.top(); q.pop(); if(vis[cur.num]) continue; vis[cur.num]=1; dis[cur.num]=cur.dis;
		for(i=head[cur.num];i;i=nex[i]) if(!vis[to[i]]) q.push((JTZ){to[i],c[i]+cur.dis});
	} return;
}
int main(){
#ifdef LOCAL
	freopen("P9377_1.in","r",stdin);
	freopen("1.out","w",stdout);
#endif
	fin>>k>>m>>s; n=(1<<k); int i,j,l,t; for(i=1;i<=k;i++) fin>>a[i];
	for(i=1;i<=m;i++){ fin>>u>>v>>w; add(u,v,w); add(v,u,w); }
	for(i=0;i<n;i++) dis[i]=a[__builtin_popcount(i^s)]; dis[s]=0;
	while(1){
		Dij();
		for(i=0;i<n;i++) for(j=1;j<=k;j++) f[i][j]=1e18;
		for(i=0;i<n;i++) f[i][0]=dis[i];
		for(l=0;l<k;l++) for(i=0;i<n;i++) if(i&(1<<l)){
			t=(i^(1<<l));
			for(j=k;j>=1;j--) f[t][j]=mmin(f[t][j],f[i][j-1]),f[i][j]=mmin(f[i][j],f[t][j-1]);
		}
		t=0;
		for(i=0;i<n;i++) for(j=1;j<=k;j++) if(f[i][j]+a[j]<dis[i]) dis[i]=f[i][j]+a[j],t=1;
		if(!t) break;
	}
	Dij();
	for(i=0;i<n;i++) fin<<dis[i]<<" \n"[i==n];
	return 0;
}