Grape Arbor Escape

You find yourself stranded on a massive grape arbor. There are exactly $2^k$ lilies, numbered from $0$ to $2^k-1$, and $m$ grape vines. The $i$-th grape vine connects the lilies numbered $x_i$ and $y_i$.

You can traverse the $i$-th grape vine in either direction at a cost of $c_i$. In addition, you have the ability to teleport between any two lilies $x$ and $y$ at a cost of $a_{d}$, where $d$ is the number of bits in which the binary representations of $x$ and $y$ differ, i.e. $$d = \mathrm{popcount}(x \oplus y).$$ For example, the binary representations of $3$ (which is $011$) and $5$ (which is $101$) differ in two positions, so teleporting between them costs $a_2$.

Assuming you start on the lily numbered $s$, compute the minimum time required to reach every lily.

inputFormat

The input consists of several lines. The first line contains three integers $k$, $m$, and $s$, where $n=2^k$ is the total number of lilies. Each of the next $m$ lines contains three integers $x_i$, $y_i$, and $c_i$, describing a grape vine connecting lilies $x_i$ and $y_i$ with cost $c_i$. The last line contains $k+1$ integers: $a_0, a_1, \dots, a_k$, representing the teleportation costs according to the number of different bits.

outputFormat

Output a single line with $n$ space-separated integers, where the $i$-th integer is the minimum time to reach the lily numbered $i$ from lily $s$.

sample

2 2 0
0 1 3
1 2 2
0 1 5

0 1 1 2