背景

译自 NWERC 2018 D 题。

题目描述

Richard 和 Janet 即将进行第一次约会。Richard 提议骑自行车去 Janet 家接她，Janet 告诉他，她会在准备好时打电话，而准备好大约需要 $10$ 到 $20$ 分钟。

但 Richard 是个没有耐心的人；他当然可以在家里等 Janet 的电话，但也可能提前出门，在附近骑一会儿，以便在 Janet 打电话后尽量缩短到达她家的时间。由于他很急躁，一旦上了自行车，他就不想低于法定限速骑行、不想在路口停下，也不想在 Janet 家门口等（不过他不介意经过 Janet 家，然后之后再回来）。

给定表示 Richard 和 Janet 家附近街区的有向图，Richard 想设计一条在附近骑行的路线（可以先在自己家等待一段时间），使得在最坏情况下 Janet 需要等待的时间最小。他可以骑任意久，也可以任意多次经过同一个路口。

Janet 准备好后会立刻给 Richard 打电话，此时 Richard 会沿他能选择的最短路径去她家。Richard 不知道 Janet 的准确准备时间，但他知道这个时间会在 $a$ 到 $b$ 分钟之间（不一定是整数分钟）。

如果 Richard 正好在 Janet 打电话的瞬间经过某个路口，则认为电话发生在他选择下一步行动之前。例如，如果他在 Janet 打电话的瞬间正好经过 Janet 家，那么他可以立即停在那里，Janet 不需要等他。

可能出现这样的情况：Janet 实际上永远不需要等待 $w$ 分钟，但如果她在某个非常不巧的时刻打电话（例如 Richard 刚离开某个路口后的几纳秒），她可能需要等待任意接近 $w$ 的 $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 在最坏情况下需要等待的时间。可以证明，最坏等待时间一定是整数。

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

6

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

5

提示

【数据规模与约定】

具体限制见输入格式。