#include<bits/stdc++.h> using namespace std; #define pb push_back #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; 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,cnt,a[MAXN]; struct nd{int x,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; queue<nd>q; int mp(int x,int y,int z){return y*k*n+z*n+x;} int dis[1<<N][N][N]; bool vis[1<<N][N][N]; inline void DP(int x,int y,int z,int sx,int sy,int 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})),cnt++; else dis[x][y][z]=dis[sx][sy][sz]+w,q.push((nd){x,y,z}); } } 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,y=Q.top().sc.y,z=Q.top().sc.z;Q.pop(); if(vis[x][y][z])continue;vis[x][y][z]=1;cnt++; 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); } while(!q.empty()){ int x=q.front().x,y=q.front().y,z=q.front().z;q.pop(); if(vis[x][y][z])continue;vis[x][y][z]=1; 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; }