## City Travel

View as PDF

Points: 15 (partial)
Time limit: 1.0s
Memory limit: 512M

Problem type

In Bob's country, there are cities, numbered from to . For any two cities and , there is an undirected road connecting city and city with a length of , where is a given constant integer, and represents the bitwise xor operation. Apart from these undirected roads, there are also one-way highways. The -th highway is from city to city with a length of .

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

#### Input Specification

The first line contains three integers , , and (, , ), representing the number of cities, the number of highways, and the constant integer , respectively.

Each of the following lines contains three integers , , and (, ), representing a one-directional highway from cities to with a length of .

The last line contains two integers and , (), representing the start city and the destination city.

#### Output Specification

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

#### 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 to city with a length of .

#### 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 to city , then take the highway from city to city , and finally take the undirected road from city to city with a total length of .