Richard 和 Janet 准备进行他们的第一次约会。Richard 提议骑自行车去 Janet 家接她，Janet 告诉他，她会在 10 到 20 分钟内准备好并给他打电话。但 Richard 是个急性子；虽然他可以在家等待 Janet 的信号，但他也可以选择提前出发，在附近骑行一会儿，以尽量缩短 Janet 在她打电话后等待他的时间。由于他的急躁，一旦 Richard 开始骑行，他就不想以低于法定限速的速度行驶、在路口停留，或者在 Janet 家门外等待（但他不介意经过 Janet 家后再绕回来）。

给定表示 Richard 和 Janet 家附近街区的有向图，Richard 希望设计一条在街区中的路线（在自家进行可选的等待后），使得 Janet 在最坏情况下的等待时间最小化。他可以随心所欲地骑行，并且可以多次经过每个路口。

Janet 一准备好就会给 Richard 打电话，届时 Richard 将采取他能选择的最短路径前往她那里。Richard 不知道 Janet 具体会在什么时候准备好，但他知道时间会在 $a$ 到 $b$ 分钟之间（不一定是整数分钟）。

如果 Richard 在 Janet 打电话的瞬间恰好经过一个路口，则视为在他在路口做出选择之前接到了电话。例如，如果他在 Janet 打电话的瞬间经过 Janet 家，他可以立即停下来，这样 Janet 就完全不需要等待他。

可能出现这种情况：Janet 从来不需要等待 $w$ 分钟，但如果她在某个不凑巧的时刻（比如离开路口后的几纳秒）给 Richard 打电话，她可能需要等待 $w - \epsilon$ 分钟（对于任意小的 $\epsilon > 0$）。在这种情况下，我们仍然将最坏情况下的等待时间定义为 $w$。

输入格式

输入包含： 一行，包含两个整数 $a, b$ ($0 \le a \le b \le 10^{12}$)，表示 Janet 将在至少 $a$ 分钟且至多 $b$ 分钟内准备好。 一行，包含两个整数 $n, m$ ($2 \le n \le m \le 10^5$)，表示街区中的路口数量和道路数量。路口编号为 $1$ 到 $n$。 * $m$ 行，每行包含三个整数 $u, v$ 和 $t$ ($1 \le u, v \le n, 1 \le t \le 10^6$)，表示有一条从路口 $u$ 到路口 $v$ 的单向道路，Richard 沿这条路行驶恰好需要 $t$ 分钟。

Richard 的家在路口 $1$，Janet 的家在路口 $n$。保证从 Richard 的家到 Janet 的家是可达的，并且保证每个路口至少有一条出路，即使该路只是绕回同一个路口。

输出格式

输出在 Janet 将在至少 $a$ 分钟且至多 $b$ 分钟内准备好，且 Richard 规划了最优路线的情况下，Janet 在最坏情况下的等待时间。

可以证明，最坏情况下的等待时间总是一个整数。

样例

样例输入 1

10 20
3 5
1 3 7
2 1 1
2 3 2
2 3 5
3 2 4

样例输出 1

6

样例输入 2

4 10
5 7
1 4 6
4 5 5
4 5 3
5 5 30
1 2 1
2 3 1
3 2 1

样例输出 2

5