企鹅国中有 N 座城市，编号从 1 到 N。
对于任意的两座城市 i 和 j，企鹅们可以花费 (i \oplus j) \times C 的时间从城市 i 走到城市 j，这里 C 为一个给定的常数。
当然除此之外还有 M 条单向的快捷通道，第 i 条快捷通道从第 F_i 个城市通向第 T_i 个城市，走这条通道需要消耗 V_i 的时间。
现在来自 Penguin Kingdom University 的企鹅豆豆正在考虑从城市 A 前往城市 B 最少需要多少时间？
企鹅国中有 N 座城市，编号从 1 到 N。
对于任意的两座城市 i 和 j，企鹅们可以花费 (i \oplus j) \times C 的时间从城市 i 走到城市 j，这里 C 为一个给定的常数。
当然除此之外还有 M 条单向的快捷通道，第 i 条快捷通道从第 F_i 个城市通向第 T_i 个城市，走这条通道需要消耗 V_i 的时间。
现在来自 Penguin Kingdom University 的企鹅豆豆正在考虑从城市 A 前往城市 B 最少需要多少时间？
从标准输入读入数据。
输入第一行包含三个整数 N, M, C（1 \le C \le 100），表示企鹅国城市的个数、快捷通道的个数以及题面中提到的给定的常数 C。
接下来的 M 行，每行三个正整数 F_i, T_i, V_i（1 \le F_i \le N，1 \le T_i \le N，1 \le V_i \le 100），分别表示对应通道的起点城市标号、终点城市标号和通过这条通道需要消耗的时间。
最后一行两个正整数 A, B，表示企鹅豆豆选择的起点城市标号和终点城市标号。
输出到标准输出。
输出一行一个整数，表示从城市 A 前往城市 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
样例 1 解释
直接从 1 走到 4 就好了。
样例 2 解释
先从 3 走到 2，再从 2 通过通道到达 4，再从 4 走到 6。