Description

There are $N$ cities in the Penguin Kingdom, numbered from $1$ to $N$.

For any two cities $i$ and $j$, penguins can spend $(i~\mathrm{xor}~j) \times C$ time to travel from city $i$ to city $j$, where $C$ is a given constant.

In addition, there are $M$ one-way express channels. The $i$-th express channel goes from city $F_i$ to city $T_i$, and taking this channel costs $V_i$ time.

Now a penguin named Doudou from Penguin Kingdom University is considering the minimum time needed to travel from city $A$ to city $B$.

Input Format

Read from standard input.

The first line of input contains three integers $N,M,C$ $(1 \leq C \leq 100)$, representing the number of cities, the number of express channels, and the given constant $C$ mentioned in the statement.

The next $M$ lines each contain three positive integers $F_i,T_i,V_i$ ($1 \leq F_i \leq N$, $1 \leq T_i \leq N, 1 \leq V_i \leq 100$), representing the start city, the end city, and the time cost of taking this channel, respectively.

The last line contains two positive integers $A,B$, representing the start city and the end city chosen by Doudou.

Output Format

Output to standard output.

Output one line with a single integer, the minimum time required to travel from city $A$ to city $B$.

4 2 1
1 3 1
2 4 4
1 4

5

7 2 10
1 3 1
2 4 4
3 6

34

Hint

Sample 1 explanation.

It is optimal to go directly from $1$ to $4$.

Sample 2 explanation.

First go from $3$ to $2$, then take the channel from $2$ to $4$, and finally go from $4$ to $6$.

The lively and lovely problem setter left everyone the picture below.

Credit: https://www.luogu.org/discuss/show/38908

Translated by ChatGPT 5