题目描述

在森林学校里面，熊大老是欺负熊二。这天，班主任光头强给小熊们带来一大袋糖果，让班长熊大分发。小熊都非常喜欢糖果，并经常将他们得到的糖果数量与其他小熊进行比较。一只小熊 $A$ 可能会有这样的想法，尽管他容忍另小熊 $B$ 得到比他更多的糖果，但无论如何，小熊 $B$ 能得到的糖果，不能比他多出 $x$ 个以上（刚好多 $x$ 个是可以的）。否则，他会感到不满意，去班主任光头强那里告状。

熊大又想欺负熊二了，他希望在让每个小熊都不去告状的同时，尽可能比熊二拿得多。请问他最多能比熊二多拿多少个？

输入格式

测试用例第一行包含两个整数 $N,M(1≤N≤30000,1≤M≤150000)$。

$N$ 是小熊的数量，小熊编号为 $1$ 到 $N$。熊二编号为 $1$，熊大编号为 $N$。

接下来有 $M$ 行，每行包含三个整数 $A,B,x$，代表小熊 $A$ 至多容许小熊 $B$ 得到的糖果数比自己多 $x(1≤x≤10000)$ 个。

输入数据保证，熊大不可能比熊二多无限多个。

输出格式

输出一个数表示答案。

2 2
1 2 5
2 1 4

5

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

4