#include<bits/stdc++.h> #define int long long #define doub long double #define PII pair<int,int> #define fir first #define sec second #define lb(x) ((x)&(-(x))) #define ctz __builtin_ctzll #define clz __builtin_clzll #define PC __builtin_popcountll #define lc(p) ((p)<<1) #define rc(p) ((p)<<1|1) #define endl '\n' using namespace std; const int N=(1<<17)+7,K=18; int k,m,s,a[K]; struct Edge{ int v,w; Edge(int _v=0,int _w=0){v=_v,w=_w;} }; struct Stat{ int u,i,j; }; vector<Edge> E[N]; bool v[N][K][K]; int Dis[N]; priority_queue<PII,vector<PII>,greater<PII>> q; queue<Stat> rq; inline void Rlx1(int u,int d){ if(Dis[u]>d)Dis[u]=d,q.push(PII(d,u)); } inline void Rlx2(int u,int i,int j){ if(!v[u][i][j])v[u][i][j]=1,rq.push((Stat){u,i,j}); } inline void Dij(int u){ for(int i=0;i<(1<<k);i++)Dis[i]=1e18; Dis[s]=0,q.push(PII(0,s)); while(!q.empty()){ int u=q.top().sec;q.pop(); for(auto e:E[u])Rlx1(e.v,Dis[u]+e.w); while(!rq.empty())rq.pop(); rq.push((Stat){u,0,0}); while(!rq.empty()){ Stat ru=rq.front();rq.pop(); if(ru.i<k){ Rlx2(ru.u,ru.i+1,ru.j); Rlx2(ru.u^(1<<ru.i),ru.i+1,ru.j+1); }else Rlx1(ru.u,Dis[u]+a[ru.j]); } } } signed main(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0); #ifndef ONLINE_JUDGE freopen("1.in","r",stdin); freopen("1.out","w",stdout); #endif cin>>k>>m>>s; for(int i=1;i<=k;i++)cin>>a[i]; for(int i=1;i<=m;i++){ int u,v,w;cin>>u>>v>>w; E[u].push_back(Edge(v,w)),E[v].push_back(Edge(u,w)); } Dij(s); for(int i=0;i<(1<<k);i++)cout<<Dis[i]<<" "; cout<<endl; return 0; }