题目描述

给出一个无向图，相邻两点之间有路径长度，求从起点到终点的路径长度对 $k$ 求余的最小值。 如下图，结点 $A$ 到结点 $D$ 路径对 $4$ 求余最小值为 $0$。

输入

第一行五个数 $n， m，k，s， t$，表示点的数目和所有点之间边的数量以及题面中的 $k$； $s，t$ 分别为起点和终点；

第二行至 $m+ 1$ 行，每行三个正整数 $u, v, w$, 分别表示点 $u$ 和 点 $v$ 之间有一条长度为 $w$ 的路径。

输出

一行一个数，要求的最小值。

样例

4 6 4 1 4
1 2 2
1 2 3
2 3 1
2 3 3
3 4 1
3 4 2

0

数据规模

$ 20 \% 的数据，2 \le n \le 10, 2 \times n \le m \le 3 \times n, 1 \le w \le 10, k \le w;$

$100 \% 的数据，2 \le n \le 1000, 2 \times n \le m \le 3 \times n, 1 \le w \le 10^{18}, k \le 10^3。$