7432: 最短路
[Creator : ]
Description
企鹅国中有 N 座城市，编号从 1 到 N。
对于任意的两座城市 i 和 j，企鹅们可以花费 $(i\,\,xor\,\, j)*C$ 的时间从城市 i 走到城市 j，这里 C 为一个给定的常数。
当然除此之外还有 M 条单向的快捷通道，第 i 条快捷通道从第 $F_i$ 个城市通向第 $T_i$ 个城市，走这条通道需要消耗 $V_i$ 的时间。
现在来自 Penguin Kingdom University 的企鹅豆豆正在考虑从城市 A 前往城市 B 最少需要多少时间？
对于任意的两座城市 i 和 j，企鹅们可以花费 $(i\,\,xor\,\, j)*C$ 的时间从城市 i 走到城市 j，这里 C 为一个给定的常数。
当然除此之外还有 M 条单向的快捷通道，第 i 条快捷通道从第 $F_i$ 个城市通向第 $T_i$ 个城市，走这条通道需要消耗 $V_i$ 的时间。
现在来自 Penguin Kingdom University 的企鹅豆豆正在考虑从城市 A 前往城市 B 最少需要多少时间？
Input
输入第一行包含三个整数 N,M,C，表示企鹅国城市的个数、快捷通道的个数以及题面中提到的给定的常数 C。
接下来的 M 行，每行三个正整数 $F_i,T_i,V_i\ (1≤F_i≤N,\ 1≤T_i≤N,\ 1≤V_i≤100)$，分别表示对应通道的起点城市标号、终点城市标号和通过这条通道需要消耗的时间。
最后一行两个正整数 $A,B\ (1≤C≤100)$，表示企鹅豆豆选择的起点城市标号和终点城市标号。
接下来的 M 行，每行三个正整数 $F_i,T_i,V_i\ (1≤F_i≤N,\ 1≤T_i≤N,\ 1≤V_i≤100)$，分别表示对应通道的起点城市标号、终点城市标号和通过这条通道需要消耗的时间。
最后一行两个正整数 $A,B\ (1≤C≤100)$，表示企鹅豆豆选择的起点城市标号和终点城市标号。
Output
输出一行一个整数，表示从城市 A 前往城市 B 需要的最少时间。
Constraints
Sample 1 Input
4 2 1
1 3 1
2 4 4
1 4
Sample 1 Output
5
直接从 1 走到 4 就好了。
Sample 2 Input
7 2 10
1 3 1
2 4 4
3 6
Sample 2 Output
34
先从 3 走到 2 ，再从 2 通过通道到达 4 ，再从 4 走到 6。