Background

At latitude 91° N, there is a magical country called the Penguin Kingdom. The penguins here have their own advanced civilization, known as the Penguin Civilization. Since penguins are only black and white, their mathematics is also based on binary.

For example, as early as $11101001$ years ago, they had the mathematical concept of XOR. If you do not know what XOR is, please go out, turn left, and head over to here.

Also, as early as $1000010$ years ago, their great scientist Penguin. Tu proposed concepts such as graph and shortest path.

Problem 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