题目描述

奥德赛岛上有n个城堡，这些城堡之间共有m条道，其中1号城堡是岛屿入口，n号城堡是岛屿出口。奥兰多打算上岛。

想要登上奥德赛岛的时间管理十分严格，开岛时间记为0时刻。从0时刻起，每间隔k单位时间才会有一艘船到达1号城堡，同时有一艘船从n号城堡离开。

所有道路只能单向通行。对于每条道路，奥兰多匀速步行的通过时间均为p单位时间。

奥兰多希望乘船到达1号城堡后，沿着自己选择的任意路径走到n号城堡，再乘船离开，这意味着他乘船到达和乘船离开城堡的时间都必须是k的非负整数倍。

奥兰多在船离开n号城堡前只想一直沿着城堡间的道路移动，而不想在任何城堡(包括1号和n号)或者道路上停留。

出发前，奥兰多忽然得知:奥德赛岛采取了限制客流的方法，对于每条道路均设置了一个“开放时间”ai，游客只有不早于ai时刻才能通过这条道路。 请帮助奥兰多设计一个方案，使得他坐船离开奥德赛岛的时间尽量地早。

输入格式

输入的第一行包含 4 个正整数 n,m,k,p，表示城堡数、道路数，发船间隔，以及奥兰多通过每条道路的时间。

输入的接下来 m 行，每行包含 3 个非负整数 ui , vi , ai 表示第 i 条道路从地点 ui出发，到达地点 vi ，道路的“开放时间”为 ai。

输出格式

输出一行，仅包含一个整数，表示奥兰多最早乘船离开奥德赛岛的时刻。如果不存在符合要求的方案，输出 -1。

5 5 3 1
1 2 0
2 5 1
1 3 0
3 4 3
4 5 1

6

样例解释

可以在 3 时刻到达1号城堡，沿 1→3→4→5 的顺序走到n号城堡，并在 6 时刻离开。

数据规模与约定

$2\leq n \leq 10^4$

$1\leq m \leq 2*10^4$

$1\leq k,p \leq 100$

$1\leq ui,vi \leq n$

$0\leq ai \leq 10^6$