https://loj.ac/s/1801476

#include <bits/stdc++.h>
#define ll long long
#define pii pair<int, int>
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define deb(var) cerr << #var << "=" << var << "; "
using namespace std;
int k, n, m, s, a[110];
vector<pii> g[(1ll << 17) + 1];
struct Node {
	int u, pos, cnt; ll dis;
	Node() {}
	Node(int a, int b, int c, ll d) {
		u = a, pos = b, cnt = c, dis = d;
	}
	bool operator < (Node b) const { return b.dis < dis; }
};
priority_queue<Node> q;
ll dis[(1ll << 17) + 1][18][18]; bool bk[1ll << 17][18][18];
void path(int s) {
	memset(dis, 0x3f, sizeof dis);
	q.push(Node(s, 0, 0, 0)); dis[s][0][0] = 0;
	while (q.size()) {
		Node t = q.top(); q.pop();
		int u = t.u, pos = t.pos, cnt = t.cnt; ll DIS = t.dis;
		if (bk[u][pos][cnt]) continue; bk[u][pos][cnt] = 1;
		if (!pos && !cnt) {
			for (int i = 0; i < g[u].size(); i++) {
				int v = g[u][i].fi, w = g[u][i].se;
				if (dis[v][0][0] > DIS + w && !bk[v][0][0]) {
					dis[v][0][0] = DIS + w; q.push(Node(v, 0, 0, DIS + w));
				}
			}
		}
		if (pos >= k) {
			int v = u, vp = 0, vc = 0; ll vd = DIS + a[cnt];
			if (vd < dis[v][vp][vc] && !bk[v][vp][vc]) {
				dis[v][vp][vc] = vd; q.push(Node(v, vp, vc, vd));
			}
		} else {
			int v = u, vp = pos + 1, vc = cnt; ll vd = DIS;
			if (vd < dis[v][vp][vc] && !bk[v][vp][vc]) {
				dis[v][vp][vc] = vd; q.push(Node(v, vp, vc, vd));
			}
			v = u ^ (1ll << pos), vp = pos + 1, vc = cnt + 1, vd = DIS;
			if (vd < dis[v][vp][vc] && !bk[v][vp][vc]) {
				dis[v][vp][vc] = vd; q.push(Node(v, vp, vc, vd));
			}
		}
	}
}

signed main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	cin >> k >> m >> s; n = 1ll << k;
	for (int i = 1; i <= k; i++) cin >> a[i];
	while (m--) {
		int u, v, w;
		cin >> u >> v >> w;
		g[u].pb(mp(v, w)); g[v].pb(mp(u, w));
	}
	path(s);
	for (int i = 0; i < n; i++) {
		cout << dis[i][0][0] << " ";
	}
	return 0;
}