题目描述

企鹅国中有 NN 座城市，编号从 11 到 NN 。

对于任意的两座城市 ii 和 jj ，企鹅们可以花费 (ixorj)×C**(i xor j)×C 的时间从城市 ii** 走到城市 jj ，这里 CC 为一个给定的常数。

当然除此之外还有 MM 条单向的快捷通道，第 ii 条快捷通道从第 FiFi​​​ 个城市通向第 TiTi​​​ 个城市，走这条通道需要消耗 ViVi​​​ 的时间。

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

输入格式

从标准输入读入数据。

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

接下来的 MM 行，每行三个正整数 Fi,Ti,ViFi​,Ti​,Vi​​ (1≤Fi≤N1≤Fi​≤N,1≤Ti≤N,1≤Vi≤1001≤Ti​≤N,1≤Vi​≤100)，分别表示对应通道的起点城市标号、终点城市标号和通过这条通道需要消耗的时间。

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

输出格式

输出到标准输出。

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

输入输出样例

输入 #1

4 2 1
1 3 1
2 4 4
1 4

输出 #1

5

输入 #2

7 2 10
1 3 1
2 4 4
3 6

输出 #2

34