测试数据来自 system/1972

背景

又是两个多月，拉尔法没有出现过，不过我们都已知道他的出现只是时间问题。两个月来我的研究工作进展神速，SE得到拉尔法的第二阈值也成为时间问题了。这个值只有在气压低到一定程度时才存在，并且第一阈值就是它的上界。所以只要算得这个气压值，问题就解决了。
“当紫电穿风刺作用于远距离的对手时，其机动性消失殆尽。即使所有的光子都产生了电能，威力惊天动地，但只有威力的招数向来是最没威力的，”棂记录道，“但除此招外，我别无选择。打消耗战于我不利，援兵肯定被挡在外面了，只能放手一搏。”
这就是我在窗边看到的一幕。我的电脑马上就能算出拉尔法的第二阈值了，棂本来是和晓筱来我这里准备“分享喜悦”的，从GQT总部讨论SE和GQT合作问题的挚友X也要回来了，估计一会儿就能到。但是：
整栋楼突然一片混乱。
晓筱：“似乎只是几个毛贼而已，我去对付。”
棂早已野猫般地跳出窗外。
晓筱叹了口气：“好吧，我去疏散人群。”
屏幕上的进度条又加了几个万分点。
棂甚至用徒手搏斗击败了使用低级法术的“小毛贼”们。他虽然法力受损，不过武功还是有相当的水平。
我一边暗暗叫好，一边按规定打开作战系统监测棂的生命指数。那是一条条平稳的曲线。突然，窗外传来一阵令人恐怖的声音：“吸积灼射！”随即，曲线出现了剧烈的异常波动。
拉尔法：“被人从背后袭击的感觉还不错吧？”
棂：“可恶！”
我一把抓过通讯器，喊道：“晓筱快回来，拉尔法出现了！”
“啊什么？！好我马上过去。等等这里有一个力场把你们隔在里面了！我先想办法破掉它。”
“棂受伤了，我先想办法顶一会儿，你快点啊！”
棂：“必杀技——紫电穿风刺！”
“看来你是不见棺材不落泪啊，”拉尔法聚集能量，“乱·魔龙舞！”
拉尔法一招化掉了棂所有的电能，这才露出了真面目：“必杀技——紫焰流毒！”
高手的必杀技令人望而生畏，却往往带着最迷人的紫色。
窗外响起了爆裂的声音，棂的生命指数曲线不再是波动了，而是急剧下降。这表明棂已经受了重伤。

描述

棂吐血三尺，正用剑拄着地面，艰难地撑着自己不倒下。
拉尔法狂妄地笑着：“这就是你上次偷袭我的代价！”
细如雨丝的鲜血悬浮在空中，在我眼前染出一片淡淡的红。
但此时我收到了计算请求。
棂：“你只管算，否则可能真的没有机会了！”
棂要使用禁术“血雾绝杀”。战斗中被打吐血几乎可以说是战败了，但自己的血里本身就蕴含着属于自己的力量。
棂的血雾已扩散到足够远，但拉尔法不知道自己已身处棂的最后一个陷阱中。客观上来讲这确实是一个好机会，不过要抓住它必定要付出惨痛的代价。
棂要给n个点分配合适的势能以达到绝杀的目的。
何谓“合适”？就是势能要同时满足m条关系。若一个关系是<a,b,c>，那么a点就必须比b点少分配至少c的势能。
每个点的势能当然不能是负的。
分配势能需要消耗法力，显然棂此时要消耗最少的法力完成分配。
棂只关心自己最少需要拿出多少势能，才能使n个点分配的势能“合适”。至于每个点具体要分配多少的问题，符咒会解决。
你能帮我吗？
要快，我只能等10s。

格式

输入格式

第一行为两个整数n和m，表示有n个点需要分配势能，有m条需要满足的关系。
接下来m行，每行3个整数a，b，c，代表点a要比点b少分配至少c点势能。

输出格式

只有一行，为所需要的最小总势能。如果无解，请输出“-1”（不含引号），不过那样的话棂真是太不幸了。

样例1

样例输入1

5 8
1 2 0
2 1 0
3 2 1
1 4 1
5 4 0
4 5 0
3 5 1
1 5 1

样例输出1

6

样例2

样例输入2

3 3
1 2 1
2 3 1
3 1 1

样例输出2

-1

限制

对于40%的数据，1≤n,m≤10^3,c≤10；
对于100%的数据，1≤n,m≤10^5,c≤100；

提示

• 样例一，最少时要给这5个点分别分配1、1、0、2、2的势能。 样例二，显然无解。
• 这个题还用不着写高精度。
• 棂通常很幸运，所以不会有多少“-1”。
• 【后记】 棂很幸运，成功发动了血雾绝杀；但他也很不幸，因为法力实在不够，攻击力连第一阈值也没有达到。 血雾渐渐散去，棂倒在地上，就连一直紧握着剑的手，也松开了。 进度条终于满了。 296.9？怎么这么低？ 窗外，拉尔法正准备彻底消灭棂。看他手中的那团火焰，是幻炎？ 晓筱还没到。 我不由得攥紧了拳头，心想：“可恶，我就算不会战斗，也要跟你拼了！” 拉尔法：“幻炎烈狱！” 那团火焰从拉尔法的手心升起，径直扑向棂。 我抄起铁枪，从窗口飞身跃下：“必杀技——狂龙穿心破！” 我喘着粗气，目送火焰被我的枪尖推向了另一个方向。火焰砸到墙上，钢筋水泥碎了一地。 这一招几乎用尽了我全身的力气，却仅仅推开了拉尔法的能量。 拉尔法：“还有人陪葬？” 我：“我劝你不要高兴太早。扩散术，目标气压296.8！” X擎刀突破力场，前来支援：“必杀技——白烈风震！” 拉尔法暗叫不妙，抽身便走。白烈风震晚了一步，未伤及他的要害，只达到了第一阈值。 晓筱也冲进来。 此时棂的生命正在消逝，众人束手无策。 X尝试用阵法封住伤口，但失败了。“伤得太重，根本止不住。” “哥，哥你别吓我……”豆大的泪珠从晓筱的脸颊上滑落。 “大家先别慌，我有衡玉。”是药师思琦！ 思琦借衡玉的力量发动治疗系法术“沉水润心”，控制住了棂的伤势。“棂只是法力消耗过度，受的伤其实没什么大碍的。好好养几天，他就能很快恢复。” 我长舒了一口气，晓筱破涕为笑。 X被惊得目瞪口呆：“起死回生？你们SE什么时候连药师都有了？” …………