Background

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

For example, as early as $11101001$ years ago, they had the mathematical concept of XOR. If you don't know what XOR is, please go outside, pass through the wall, and turn left to here.

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

Problem Description

In Penguinland, there are $N$ cities, numbered from $1$ to $N$.

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

In addition to this, there are $M$ one-way fast tracks. The $i$-th fast track connects city $F_i$ to city $T_i$ and requires $V_i$ time to travel.

Now, Penguin DouDou from Penguin Kingdom University is considering the minimum time required to travel from city $A$ to city $B$.

Input Format

Read from standard input.

The first line contains three integers $N, M, C$, representing the number of cities in Penguinland, the number of fast tracks, and the constant $C$ mentioned in the problem.

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 starting city, ending city, and time required for the corresponding fast track.

The last line contains two positive integers $A, B$ ($1 \leq C \leq 100$), representing the starting city and ending city chosen by Penguin DouDou.

Output Format

Output to standard output.

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

Sample Input and Output

Sample Input #1

4 2 1
1 3 1
2 4 4
1 4

Sample Output #1

5

Sample Input #2

7 2 10
1 3 1
2 4 4
3 6

Sample Output #2

34

Notes

Sample 1 Explanation

Just travel directly from city $1$ to city $4$.

Sample 2 Explanation

First travel from city $3$ to city $2$, then from city $2$ to city $4$ via the fast track, and finally from city $4$ to city $6$.

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

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

见题面 Input 部分

见题面 Output 部分