问题 26096 --抢糖果

26096: 抢糖果

时间限制: 1 Sec  内存限制: 128 MB
提交: 28  解决: 20
[提交][状态][讨论版][数据上传:][下载FPS1元][下载测试数据1元][23056kb]

题目描述

[前面提到的糖人即糖人1]
当小Y从糖果峡谷走出以后,正为自己拿到的糖果而高兴。
正所谓,福兮,祸之所倚。糖人1又出现了,而且还很气愤!!糖人1说:“你拿了太多的糖果,会影响糖果世界的平衡,我不能允许这样的事情出现!”。于是,糖人1向小Y要了很多糖果,小Y无奈,只得交出糖人要求的糖果,谁让这是人家的地盘,于是,小Y便带着剩下的糖果离开了这里。
糖人1回到糖人部落后,其他糖人知道糖人1获得了很多糖果,纷纷来索要糖果,他们分别是糖人2,糖人3,糖人4•••••••糖人n。糖人们都有一个要求,有的糖人觉得糖人1太辛苦就没有提要求,而有的糖人由于糖人之间的私人恩怨,会提很多要求。一共有m个要求,即糖人u要求自己的糖果数最多比糖人v少w。
小Y交出的糖果本来应该由糖人1来分配,但由于糖人n的威望比糖人1高,所以糖果由糖人n来分配。糖人n希望自己在满足众多糖人要求后,获得的糖果能比糖人1尽量多,问最多能多多少个糖果。

输入

第一行,两个整数n,m表示有n个糖人,m个要求
接下来m行,每行三个数u,v,w

输出

输出仅一行,糖人n最多能比糖人1多多少个糖果。

样例输入

2 2
1 2 5
2 1 4

样例输出

5

提示


【样例说明】



    样例中只有两个糖人,我们称 糖人2 为 糖人n 。假设 糖人1 1 个糖果, 糖人n 在满足 “糖人1 最多比 糖人n 5 个糖果” 的条件下,最多糖果数目为 6 ,而此时也满足了 “糖人n 最多比 糖人1 4 个糖果” 的条件(因为 糖人n 比 糖人1 糖果多,也可以看做 糖人n 比 糖人1 -5 个糖果),所以 糖人n 最多比
糖人1 5个糖果。



【数据范围】



      






















30%




n<=5000




m<=25000




50%




n<=10000




m<=60000




100%




n<=30000




m<=150000




保证所有结果不会超过32位整型。

来源

[提交][状态]