题目描述

在北纬 $91°$ ，有一个神奇的国度，叫做企鹅国。这里的企鹅也有自己发达的文明，称为企鹅文明。因为企鹅只有黑白两种颜色，所以他们的数学也是以二进制为基础发展的。

比如早在 $11101001$ 年前，他们就有了异或这样一个数学概念。如果你不知道异或是什么，请出门过墙左转到这里。

再比如早在 $1000010$ 年前，他们的大科学家 Penguin. Tu 就提出了图和最短路径这样一些概念。

企鹅国中有 $N$ 座城市，编号从 $1$ 到 $N$ 。

对于任意的两座城市 $i$ 和 $j$ ，企鹅们可以花费 $(i~\mathrm{xor}~j) \times C$ 的时间从城市 $i$ 走到城市 $j$ ，这里 $C$ 为一个给定的常数。

当然除此之外还有 $M$ 条单向的快捷通道，第 $i$ 条快捷通道从第 $F_i$ 个城市通向第 $T_i$ 个城市，走这条通道需要消耗 $V_i$ 的时间。

现在来自 Penguin Kingdom University 的企鹅豆豆正在考虑从城市 $A$ 前往城市 $B$ 最少需要多少时间？

输入格式

从标准输入读入数据。

输入第一行包含三个整数 $N,M,C$ ，表示企鹅国城市的个数、快捷通道的个数以及题面中提到的给定的常数C。

接下来的 $M$ 行，每行三个正整数 $F_i,T_i,V_i$ $(1 \leq F_i \leq N , 1 \leq T_i \leq N , 1\leq V_i \leq 100 )$，分别表示对应通道的起点城市标号、终点城市标号和通过这条通道需要消耗的时间。

最后一行两个正整数 $A,B$ $(1 \leq C \leq 100 )$，表示企鹅豆豆选择的起点城市标号和终点城市标号。

输出格式

输出到标准输出。

输出一行一个整数，表示从城市 $A$ 前往城市 $B$ 需要的最少时间。

样例 1

4 2 1
1 3 1
2 4 4
1 4

5

直接从 $1$ 走到 $4$ 就好了。

7 2 10
1 3 1
2 4 4
3 6

34

先从 $3$ 走到 $2$ ，再从 $2$ 通过通道到达 $4$ ，再从 $4$ 走到 $6$。

数据范围与提示

活泼可爱的出题人给大家留下了下面这张图。

来自 CodePlus 第 4 次月赛，清华大学计算机科学与技术系学生算法与竞赛协会 荣誉出品。
Credit：idea 与命题/吴凯路　验题/张瀚文
Git Repo：https://git.thusaac.org/publish/CodePlus4
感谢腾讯公司对此次比赛的支持。