Penguin Kingdom Travel Time

In Penguin Kingdom, there are $N$ cities, numbered from $1$ to $N$. For any two distinct cities $i$ and $j$, a penguin can travel from $i$ to $j$ in ( (i \oplus j) \times C ) time (where ( \oplus ) denotes the bitwise XOR operation and $C$ is a given constant). Additionally, there are $M$ one-way shortcut channels. The $i$-th shortcut channel runs from city $F_i$ to city $T_i$ and takes $V_i$ time. Given two cities $A$ and $B$, determine the minimum time required to travel from city $A$ to city $B$.

inputFormat

The first line contains five integers: $N$, $M$, $C$, $A$, and $B$. Each of the following $M$ lines contains three integers $F_i$, $T_i$, and $V_i$, describing a shortcut channel from city $F_i$ to $T_i$ with time cost $V_i$.

outputFormat

Output a single integer representing the minimum time required to travel from city $A$ to city $B$.

sample

4 1 1 1 4
2 3 1

5