Problem Y: 超级简单

Problem Y: 超级简单

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 5  Solved: 2
[Submit] [Status] [Web Board] [Creator:]

Description

奥利奥的王国中有N座城市,编号从1到N。
对于任意的两座城市i和j,企鹅们可以花费(i^j)x C的时间从城市i走到城市j,C是一个常数。
还有M条单向的传送门。

Input

输入第一行包含三个整数N,M,C,表示王国城市的个数、传送门的个数以及题面中提到的给定的常数C。
接下来的M行,每行三个正整数a,b,c(1≤a≤N,1≤b≤N,1≤c≤100),分别表示对应传送门的起点城市标号、终点城市标号和通过这条通道需要消耗的时间。
最后一行两个正整数A,B(1≤C≤100),表示奥利奥选择的起点城市标号和终点城市标号。
N<=1e5,M<=5e5.

Output

输出奥利奥从起点到终点消耗的最小时间。

Sample Input Copy

4 2 1
1 3 1
2 4 4
1 4

Sample Output Copy

5