测试数据来自 system/1694

背景

在经历了Nobody煎熬的一个星期后......
F最近一直在看<守护甜心>(画外音:还看这个!F,你Out了!F:怀旧一下嘛...再说也不是很旧),并且深深沉迷于其中的天才歌手星那歌呗(不知道?百度一下啦~~)的歌声.正在此时,葱歌......又出现了......
葱歌:哇,这个女孩子好漂亮!是谁啊是谁啊?
F(= =||):星那歌呗.
葱歌:她唱的什么歌?好好听我也要唱!
F(= =+):Black Diamond.你别把Bad Eggs召唤出来......
葱歌:呃...这是要条件的......如果你又想听这首歌又想不碰到Bad Eggs的话,要回答我的问题哦~~
F(= =#):又来了...交给你了,屏幕前的那位!

描述

葱歌:听好了哦~~
葱歌最近呢,碰到了一个棘手的问题!葱歌在梦里(虚拟人也会做梦?)遇到了一个迷宫.这个迷宫不是用来走的.整个迷宫有N个路口和M条路.每条路连接两个路口,并且是单向的.
这个迷宫被一个名叫Virus的病毒控制着,如果不破坏它的话,Virus就会用这个迷宫干扰初音唱歌.而破坏它的条件是当且仅当这个迷宫存在一条能够遍历其的欧拉路.因此葱歌不得不再次使用力量把其中的一些边破坏掉,使得这个迷宫存在一条遍历它的欧拉路.葱歌的力量有限,因此她希望破坏边所花总代价越少越好.请你告诉她,最小要多少代价呢?
葱歌:还有还有,还没说完呢!某个路口如果没路了,这个路口就会自动消失哦~~

格式

输入格式

输入第一行两个正整数n,m.表示有n个路口,m条路.
接下去m行,每行3个正整数a,b,w.表示一条a通向b的路以及破坏这条路所需的能量.

输出格式

一行一个正整数min,表示破坏这个迷宫所需的最少能量.注意当迷宫满足被破坏的条件之后就会被杀毒软件瞬间灭掉,不需葱歌的能量.

样例1

样例输入1

4 5
2 4 664766
1 2 807980
1 4 645253
4 1 983783
3 2 775081

样例输出1

645253

限制

1s

提示

对于100%的数据,1<=n<=30,1<=m<=50.

来源

<Black Diamond>By 水树奈奈
告诉我你最想说的誓言
你最想要的东西
象打开音量般的刺耳
大声喊叫着
趁太阳还没升起来
世界 开始吧
与光影跳舞
是的 牵着你的手
来 你想要什么？想得到什么？
积攒的光辉 在那手上
全都可以得到 在这肮脏的夜空
Black Diamond Black Diamond
颤抖的手 捧出祈祷
是你想要的
好像没有生机的玩偶哦
连眼泪都不会流
哪怕是受伤 哪怕都是谎言
也绝不辩解
都是真的 闪烁着
违背看不到的力量
来 唱什么？相信什么？
如果迷茫 就自暴自弃
全都丢在脑后 在这歪曲的夜空
Black Diamond Black Diamond
来 你想要什么？想得到什么？
积攒的光辉 在那手上
都可以得到 在这扭曲的夜空
Black Diamond Black Diamond
......over