#include<bits/stdc++.h> using namespace std; #define pb push_back #define sht short #define pii pair<int,int> #define fr first #define sc second #define mk make_pair #define inx(u) int I=h[(u)],v=edge[I].v,w=edge[I].w;I;I=edge[I].nx,v=edge[I].v,w=edge[I].w #define popcnt __builtin_popcount const int MAXN=200010,N=18; namespace INPUT_SPACE{ const int S=(1<<20)+5;char B[S],*H,*T;inline int gc() { if(H==T) T=(H=B)+fread(B,1,S,stdin);return (H==T)?EOF:*H++; } inline unsigned int read() { unsigned int x,ch;while((ch=gc())<'0'||ch>'9');x=ch^'0';while((ch=gc())>='0'&&ch<='9') x=x*10+(ch^'0');return x; } }using INPUT_SPACE::read; // int read(){int x=0,f=1;char c=getchar();while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();return x*f;} bool AAA; struct Edge{int v,nx,w;}edge[MAXN<<1];int h[MAXN],CNT;void add_side(int u,int v,int w){edge[++CNT]={v,h[u],w};h[u]=CNT;} int k,n,m,s,a[MAXN]; struct nd{int x;sht y,z;bool operator<(const nd&G)const{return x!=G.x?x<G.x:y!=G.y?y<G.y:z<G.z;}}; priority_queue<pair<int,nd>>Q; nd q[MAXN];int cnt; int dis[1<<N][N][N]; bool vis[1<<N][N][N]; inline void DP(int x,sht y,sht z,int sx,sht sy,sht sz,int w){ if(y<z||vis[x][y][z])return; if(dis[x][y][z]>dis[sx][sy][sz]+w){ if(w)dis[x][y][z]=dis[sx][sy][sz]+w,Q.push(mk(-dis[x][y][z],(nd){x,y,z})); else dis[x][y][z]=dis[sx][sy][sz]+w,q[++cnt]=(nd){x,y,z},vis[x][y][z]=1; } } void dji(){ memset(dis,0x3f,sizeof(dis)); dis[s][0][0]=0; Q.push(mk(0,(nd){s,0,0})); while(!Q.empty()){ int x=Q.top().sc.x;sht y=Q.top().sc.y,z=Q.top().sc.z;Q.pop(); if(vis[x][y][z])continue;vis[x][y][z]=1;cnt=0; if(!y&&!z){ for(inx(x))DP(v,0,0,x,0,0,w); for(int i=1;i<=k;i++)DP(x,k,i,x,0,0,a[i]); } if(y){ if(z)DP(x^(1<<y-1),y-1,z-1,x,y,z,0),DP(x,y-1,z,x,y,z,0); else DP(x,0,0,x,y,z,0); } for(int o=1;o<=cnt;o++){ int x=q[o].x,y=q[o].y,z=q[o].z; if(!y&&!z){ for(inx(x))DP(v,0,0,x,0,0,w); for(int i=1;i<=k;i++)DP(x,k,i,x,0,0,a[i]); } if(y){ if(z)DP(x^(1<<y-1),y-1,z-1,x,y,z,0),DP(x,y-1,z,x,y,z,0); else DP(x,0,0,x,y,z,0); } } } } void slv(){ k=read(),m=read(),s=read(),n=1<<k; for(int i=1;i<=k;i++)a[i]=read(); for(int i=1;i<=m;i++){ int u=read(),v=read(),w=read(); add_side(u,v,w); add_side(v,u,w); } dji(); for(int i=0;i<n;i++)printf("%d ",dis[i][0][0]); } bool BBB; signed main(){ // freopen("1.in","r",stdin);freopen("1.out","w",stdout); slv(); //cerr<<clock()*1.0/CLOCKS_PER_SEC<<"s\n"<<((&AAA)-(&BBB))/1024.0/1024<<"MB\n"; return 0; }