{"trustable":false,"sections":[{"title":"题目描述","value":{"format":"MD","content":"在贝尔星球,所有的幼崽都要送进幼体认知协调初级培训中心。在那里小卡波被任命为卡波培训集成小组(后简称为卡波组)认知协调助手。偶尔,该小组的认知协调员会给卡波组的幼崽们带来一大箱蜜罐,让小卡波分发。所有的幼崽都非常喜欢蜂蜜,并且经常把他们得到的蜜罐数量与其他人进行比较。一个幼崽A可能会有这样的想法,虽然另一个幼崽B在某些方面可能比他更先进,因此有理由比他拿到更多的蜜罐,但无论他实际拿到多少蜜罐,他都不应该比B少拿一定数量的蜜罐,否则,他会感到不满意,并去找认知协调员抱怨小卡波分蜜罐不公平。\n史努比当时和小卡波一起接受认知协调。小卡波总是比较他的蜜罐和史努比的蜜罐的数量。他想在让每个幼崽都满意的情况下,让所有幼崽在比较时蜜罐数量差的最大值尽可能大。现在他刚从认知协调员那里得到了另一袋蜜罐,他想知道这个蜜罐数量差的最大值是多少?\n"}},{"title":"输入格式","value":{"format":"MD","content":"输入只包含一组测试数据。测试数据的第一行包括两个整数 $N$ 和 $M$($N\\leq 30000$ 且 $M\\leq 150000$)。$N$ 是小组内幼崽的数量,幼崽们的编号从 $1$ 到 $N$ 。史努比和卡波总是被编号为 $1$ 和 $N$ 。接下来 $M$ 行,每个行依次包含三个整数 $A$ 、 $B$ 和 $C$ ,这意味着幼崽 $A$ 认为幼崽 $B$ 不会比他多拿 $C$ 个蜜罐。"}},{"title":"输出格式","value":{"format":"MD","content":"输出只有一行,是幼崽们之间比较时的蜜罐差的最大值,输入数据保证这个值是有限大的。\n保证所有的数据在int范围内。"}},{"title":"样例输入","value":{"format":"MD","content":"2 2\n1 2 5\n2 1 4\n"}},{"title":"样例输出","value":{"format":"MD","content":"5"}}]}