1887. 小孩子有两个属性

单点时限: 4.0 sec

内存限制: 256 MB

小孩子有两个属性:喜欢吃糖果和爱耍小孩子脾气,当两个结合在一起有什么效果?答案:一道题产生了。

你要把糖果分给 N 个小朋友,分配完后,每个小朋友会把自己得到的糖果数与某个小朋友进行比较,当他比较的人的糖果数比他的糖果数多到一定数量时,小孩的第二个属性就显现出来了。为了不使小孩幼小的心灵受到创伤,你要兼顾各个小孩的情况,做出适当的分配。

输入格式

单组测试数据。以两个数 N(1<=N<=30000),M(1<=M<=150000) 开始,表示有 N 个小孩需要糖果。接下来 M 行每行有三个整数 A,B,C,表示该次比较发生在 A 与 B 之间,小孩 A 的最大忍耐限度是小孩 B 得到的糖果数比自己多 C 个。

输出格式

输出小孩 N 比小孩 1 最多多得多少个糖果。

样例

Input
2 2
1 2 5
2 1 4
Output
5
Hint:
结果在signed int 范围。

24 人解决,74 人已尝试。

37 份提交通过,共有 391 份提交。

6.8 EMB 奖励。

创建: 12 年,7 月前.

修改: 3 年,3 月前.

最后提交: 8 月,3 周前.

来源: N/A

题目标签