Background

Lilies cannot bloom on grapevines.

Problem Description

You land on a huge grape trellis. There are $2^k$ lilies and $m$ grapevines on it. The lilies are labeled with integers from $0$ to $2^k-1$. The $i$-th grapevine connects lilies $x_i$ and $y_i$.

You can spend $c_i$ time to travel along the $i$-th grapevine, i.e., from $x_i$ to $y_i$ or vice versa. You can also spend $a_k$ time to teleport from $x$ to $y$, where $x$ and $y$ are any two lilies, and $k$ is the number of differing bits in their binary representations. For example, the binary representation of $3$ is $011$, and the binary representation of $5$ is $101$. They differ in two bits, so teleporting from $3$ to $5$ costs $a_2$ time.

Suppose you land exactly on the lily labeled $s$. Find the shortest time needed to travel from $s$ to every lily.

Input Format

The first line contains three positive integers $k, m, s$, as described above.

The second line contains $k$ non-negative integers $a_i$, representing the time cost of teleportation.

Lines $3$ to $(m+2)$ each contain three non-negative integers $x_i, y_i, c_i$.

Output Format

Output one line with $2^k$ numbers $D_i$ ($0 \leq i \leq 2^k-1$), separated by spaces, where $D_i$ is the shortest time from $s$ to $i$.

3 6 2
17 14 11 
0 2 3
4 2 9
2 2 1
2 2 6
7 0 5
4 2 9

3 14 0 17 9 11 17 8

Hint

Constraints

For all testdata, $1 \le k \leq 17$, $1 \le m \leq 2 \times 10^5$, $0 \leq s, x_i, y_i \leq 2^k - 1$, $0 \le a_i, c_i \leq 2^{30} - 1$.

Source

From the 2023 Tsinghua University Student Algorithmic Contest and Intercollegiate Invitational Programming Contest (THUPC2023) Finals.

Resources such as editorials can be found at https://github.com/THUSAAC/THUPC2023.

Translated by ChatGPT 5