题号：NC15479
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld
题目描述
企鹅国中有座城市，编号从
到
。
对于任意的两座城市和
，企鹅们可以花费
的时间从城市
走到城市
，这里
为一个给定的常数。
当然除此之外还有条单向的快捷通道，第i条快捷通道从第
个城市通向第
个城市，走这条通道需要消耗
的时间。
现在来自Penguin Kingdom University的企鹅豆豆正在考虑从城市前往城市
最少需要多少时间？
输入描述:
输入第一行包含三个整数N,M,C，表示企鹅国城市的个数、快捷通道的个数以及题面中提到的给定的常数C。
接下来的M行，每行三个正整数Fi,Ti,Vi(1≤Fi≤N,1≤Ti≤N,1≤Vi≤100)，分别表示对应通道的起点城市标号、终点城市标号和通过这条通道需要消耗的时间。
最后一行两个正整数A,B(1≤C≤100)，表示企鹅豆豆选择的起点城市标号和终点城市标号。
输出描述:
输出一行一个整数，表示从城市 A 前往城市 B 需要的最少时间。
