描述

在幼儿园时期，飞鼠是他所在班级的班长。偶尔班主任会给飞鼠班上的孩子们带来一大袋糖果，然后让飞鼠来分发。所有孩子都非常喜欢糖果，并且经常会比较自己和别人得到的糖果数量。对于孩子 A 来说，即使可能存在另一个孩子 B 在某些方面比他优秀，因此有理由得到比他更多的糖果，但无论他实际得到多少糖果，他得到的糖果数量永远不应该比 B 少，否则他就会感到不满并向班主任抱怨飞鼠分配不公平。

史努比当时和飞鼠同班。飞鼠总是会将自己的糖果数量和史努比的进行比较。他想在让每个孩子都满意的情况下，使自己和史努比的糖果数量差值尽可能大。现在他刚从班主任那里拿到了另一袋糖果，他最多能制造出多大的差值呢？

输入

输入包含一个测试用例。测试用例的第一行是两个整数 $N$ 和 $M，N$ 和 $M$ 分别不超过 $30000 和 150000。N$ 是班级里孩子的数量，孩子们从 $1$ 到 $N$ 编号。史努比和飞鼠的编号总是 $1$ 和 $N$。接下来有 $M$ 行，每行按顺序包含三个整数 $A、B$ 和 $c$，意思是孩子 A 认为孩子 B 得到的糖果数量比他多的部分永远不能超过 $c$ 颗。

输出

输出仅包含一个整数，表示期望的最大差值。保证该差值是有限的。

输入数据 1

2 2

1 2 5

2 1 4

输出数据 1

5

提示 32 位有符号整数类型足以进行所有运算。