你正试图到达迷宫的中心，这意味着你必须穿过“永恒恶臭沼泽”（Bog of Eternal Stench）。传说如果你在沼泽里沾上哪怕一点点恶臭，你就会永远散发恶臭……你当然希望以尽可能低的恶臭等级穿过沼泽。

幸运的是，你之前已经确定恶臭最终会消散，并且沼泽中的某些区域比其他区域会带给你更多的恶臭。还有一些小岛可以让你休息，而不会对你的恶臭等级产生任何影响。第一个岛屿是你穿越永恒恶臭沼泽旅程的起点，最后一个岛屿是你在另一侧的目的地。

从每个岛屿出发，既有的桥梁允许你前往其他岛屿，但这些桥梁只能单向通行。因为这是永恒恶臭沼泽，沿着大多数桥梁行走会使你的总体恶臭等级增加一定的数值。然而，有些桥梁非常舒适，沿着它们行走会降低你的总体恶臭等级。但这里有一个陷阱——你的恶臭等级永远不会降至 0 以下。（如果一座桥梁会使你的恶臭等级降至 0 以下，它会将恶臭等级设为 0）。

你已经仔细绘制了所有岛屿和桥梁的地图，并测量了每座桥梁增加或减少的恶臭值。因此，你或许有可能穿过永恒恶臭沼泽并最终完全没有恶臭！

你的首要任务是以最低的恶臭等级到达目的地岛屿；如果这样做能实现目标，你愿意走弯路并多次访问某些岛屿。你的路径必须在目的地岛屿结束，但如果你第一次到达目的地时并没有立即离开沼泽，且通过额外的绕路并稍后返回该岛能降低你最终的恶臭值，那么你不必在第一次到达时就离开。

输入格式

第一行包含两个整数 $n$ 和 $m$ ($1 \le n, m \le 2\,000$)，其中 $n$ 是岛屿的数量，$m$ 是直接桥梁的数量。

接下来的 $m$ 行，每行包含 3 个整数 $u, v$ 和 $s$ ($1 \le u, v \le n, -10^9 \le s \le 10^9$)，表示有一座从岛屿 $u$ 到岛屿 $v$ 的直接桥梁，它会使你的总体恶臭等级改变 $s$。保证 $u \neq v$，且从 $u$ 到 $v$ 最多只有一座直接桥梁（但可能存在从 $v$ 到 $u$ 的另一座直接桥梁）。

你可以假设从岛屿 1（起点）到达岛屿 $n$（目的地）是可能的。

输出格式

输出一个整数，即你离开沼泽时可能达到的最低恶臭等级，假设你开始时的恶臭等级为 0。

样例

样例输入 1

4 4
1 2 5
1 3 -2
2 4 1
3 4 10

样例输出 1

6

样例输入 2

5 5
1 2 1000
2 3 -3
3 4 1
4 2 0
2 5 2

样例输出 2

3

样例输入 3

3 3
1 3 -10
3 2 2
2 3 -1

样例输出 3

0