代码如下：

#include<iostream>
#include<queue>
#include<cstring>
#include<assert.h>
using namespace std;

#define fl(i,a,b) for(int i = a;i<(b);i++)
#define fg(i,a,b) for(int i = a;i>(b);i--)
#define fle(i,a,b) for(int i = a;i<=(b);i++)
#define fge(i,a,b) for(int i = a;i>=(b);i--)
#define inf 0x3f3f3f3f
#define long_inf 0x3f3f3f3f3f3f3f3f
#define ll long long
#define fi first
#define se second
#define mp make_pair
#define maxk 17
#define maxm 400005

ll k,m,s;
ll a[maxk];
ll x[maxm << 1],y[maxm << 1],c[maxm << 1];
ll head[1<<maxk],ver[maxm << 1],edge[maxm << 1],nex[maxm << 1],d[maxm << 1];
bool v[1<<maxk];
ll n,tot;
priority_queue<pair<ll,ll>> q;

void add(ll b,ll e,ll z){
    ver[++tot] = e,edge[tot] = z,nex[tot] = head[b],head[b] = tot;
}

void dijkstra(ll start){
    memset(v,0,sizeof(v));
    d[start] = 0;
    q.push(mp(0,start));
    while (q.size())
    {
        ll j = q.top().se;q.pop();
        if(v[j]){continue;}
        v[j] = 1;
        for(ll i = head[j];i;i = nex[i]){
            ll e = ver[i],z = edge[i];
            if(d[e] > d[j] + z){
                d[e] = d[j] + z;
                q.push(mp(-d[e],e));
            }
        }
    }
}

int main()
{
    // freopen("P9377.in","r",stdin);
    // freopen("P9377.ans","w",stdout);
    cin >> k >> m >> s;
    fle(i,1,k){
        cin >> a[i];
    }
    fle(i,1,m){
        cin >> x[i] >> y[i] >> c[i];
        add(x[i],y[i],c[i]),add(y[i],x[i],c[i]);
    }
    for(ll i = 0;i <= (1<<k)-1;i++){
        for(ll j = 0;j <= (1<<k)-1;j++){
            ll cnt = 0;
            if(i == j){continue;}
            fl(k,0,18){
                if(((i >> k) & 1) != ((j >> k) & 1)){
                    cnt++;
                }
            }
            if(cnt < 1&&cnt > k){continue;}
            add(i,j,a[cnt]),add(j,i,a[cnt]);
        }
    }
    memset(d,0x3f,sizeof(d));
    dijkstra(s);
    for(ll i = 0;i < (1<<k);i++){
        cout << d[i] << " ";
    }
    return 0;
}