P9377 [THUPC 2023 Finals] Lily

Lilies cannot bloom on grapevines.

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.

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 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$.

**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](https://github.com/THUSAAC/THUPC2023). Translated by ChatGPT 5