UOJ Logo 黑暗爆炸OJ

DARKBZOJ

#1808. [Ioi2007]training 训练路径

Statistics 下载数据

Description

马克(Mirko)和斯拉夫克(Slavko)正在为克罗地亚举办的每年一次的双人骑车马拉松赛而紧张训练。他们需要选择一条训练路径。 他们国家有N个城市和M条道路。每条道路连接两个城市。这些道路中恰好有N-1条是铺设好的道路,其余道路是未经铺设的土路。幸运的是,每两个城市之间都存在一条由铺设好的道路组成的通路。换句话说,这N个城市和N-1条铺设好的道路构成一个树状结构。 此外,每个城市最多是10条道路的端点。 一条训练路径由某个城市开始,途经一些道路后在原来起始的城市结束。因为马克和斯拉夫克喜欢去看新城市,所以他们制定了一条规则:绝不中途穿越已经去过的城市,并且绝不在相同的道路上骑行两次(不管方向是否相同)。训练路径可以从任何一个城市开始,并且不需要访问所有城市。 显然,坐在后座的骑行者更为轻松,因为坐在前面的可以为他挡风。为此,马克和斯拉夫克在每个城市都要调换位置。为了保证他们的训练强度相同,他们要选择一条具有偶数条道路的路径。 马克和斯拉夫克的竞争者决定在某些未经铺设的土路上设置路障,使得他们两人不可能找到满足上述要求的训练路径。已知在每条土路上设置路障都有一个费用值(一个正整数),并且竞争者不能在铺设好的道路上设置路障。 任务 给定城市和道路网的描述,写一个程序计算出为了使得满足上述要求的训练路径不存在,而需要的设置路障的最小总费用。

Input

输入的第一行包含两个整数N和M,(2≤N≤1000,N-1≤M≤5000),分别表示城市和道路的个数。 接下来的M行每行包含3个整数A, B和C(1≤A≤N, 1≤B≤N, 0≤C≤10 000), 用来描述一条道路。A和B是不同的整数,表示由这条道路直接相连的两个城市。对于铺设好的道路C是0;对于土路,c是在该条路上设置路障所需的费用值。 每个城市最多是10条道路的端点。任意两个城市都不会有多于一条直接相连的道路。

Output

输出包含一个整数,表示求出的最小总费用。

Sample Input

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

Sample Output

5

Hint

Source