In Bob's country, there are ~N~ cities, numbered from ~1~ to ~N~. For any two cities ~x~ and ~y~, there is an undirected road connecting city ~x~ and city ~y~ with a length of ~(x \oplus y) \times D~, where ~D~ is a given constant integer, and ~\oplus~ represents the bitwise xor operation. Apart from these undirected roads, there are also ~M~ one-way highways. The ~i~-th highway is from city ~u_i~ to city ~v_i~ with a length of ~w_i~.

Now, Bob wants to travel from city ~A~ to city ~B~. Can you find the shortest path for Bob?

Input Specification

The first line contains three integers ~N~, ~M~, and ~D~ (~2 \leq N \leq 10^5~, ~0 \leq M \leq 5 \times 10^5~, ~1 \leq D \leq 100~), representing the number of cities, the number of highways, and the constant integer ~D~, respectively.

Each of the following ~M~ lines contains three integers ~u_i~, ~v_i~, and ~w_i~ (~1 \leq u_i, v_i \leq N~, ~1 \leq w_i \leq 100~), representing a one-directional highway from cities ~u_i~ to ~v_i~ with a length of ~w_i~.

The last line contains two integers ~A~ and ~B~, (~1 \leq A, B \leq N~), representing the start city and the destination city.

Output Specification

Output one integer representing the length of the shortest path for Bob from city ~A~ to city ~B~.

Constraints

Subtask	Points	Additional constraints
~1~	~5~	~M = 0~
~2~	~5~	~M = 1~
~3~	~5~	~M = 3~
~4~	~5~	~M = 10~
~5~	~15~	~M = 1\,000~
~6~	~15~	~N = 1\,000~
~7~	~50~	No additional constraints

Sample Input 1

4 2 1
1 3 1
2 4 4
1 4

Sample Output 1

5

Explanation

Bob can take the undirected road from city ~1~ to city ~4~ with a length of ~(1 \oplus 4) \times 1 = 5~.

Sample Input 2

7 2 10
1 3 1
2 4 4
3 6

Sample Output 2

34

Explanation

Bob can take the undirected road from city ~3~ to city ~2~, then take the highway from city ~2~ to city ~4~, and finally take the undirected road from city ~4~ to city ~6~ with a total length of ~34~.