Mirko 和 Slavko 正在为克罗地亚举办的年度双人自行车马拉松赛进行刻苦训练。他们需要选择一条路线进行训练。

他们的国家有 $N$ 个城市和 $M$ 条道路。每条道路连接两个城市，且可以双向通行。其中恰好有 $N-1$ 条道路是铺设好的（paved），其余道路为未铺设的土路（unpaved）。幸运的是，道路网络的设计使得每对城市之间都有一条由铺设好的道路组成的路径。换句话说，这 $N$ 个城市和 $N-1$ 条铺设好的道路构成了一棵树。

此外，每个城市最多连接 10 条道路。

训练路线从某个城市出发，经过若干道路，最后回到出发的城市。Mirko 和 Slavko 喜欢看新的地方，所以他们制定了一个规则：绝不经过同一个城市，也不重复经过同一条道路。训练路线可以从任何城市开始，且不需要访问所有城市。

坐在后座的人更容易骑行，因为前座的人为他挡住了风。因此，Mirko 和 Slavko 在每个城市都会交换座位。为了确保他们获得相同的训练量，他们必须选择一条包含偶数条道路的路线。

Mirko 和 Slavko 的竞争对手决定封锁一些土路，使得他们无法找到满足上述要求的训练路线。每条土路都有一个封锁代价（正整数）。铺设好的道路无法被封锁。

题目描述

编写一个程序，给定城市和道路网络的描述，计算为了使不存在满足上述要求的训练路线，所需封锁道路的最小总代价。

输入格式

输入的第一行包含两个整数 $N$ 和 $M$ ($2 \le N \le 1000, N-1 \le M \le 5000$)，分别表示城市数量和道路总数。

接下来的 $M$ 行，每行包含三个整数 $A, B$ 和 $C$ ($1 \le A \le N, 1 \le B \le N, 0 \le C \le 10000$)，描述一条道路。$A$ 和 $B$ 是不同的，表示该道路直接连接的两个城市。如果 $C=0$，则该道路是铺设好的；否则，该道路是土路，且 $C$ 表示封锁它的代价。

每个城市最多连接 10 条道路。任意两个城市之间最多只有一条直接相连的道路。

输出格式

输出一个整数，即题目描述中封锁道路所需的最小总代价。

子任务

在总分 30 分的测试用例中，铺设好的道路将构成一条链（即没有城市连接三条或更多铺设好的道路）。

样例

样例输入 1

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

样例输出 1

5

样例输入 2

9 14 
1 2 0 
1 3 0 
2 3 14 
2 6 15 
3 4 0 
3 5 0 
3 6 12 
3 7 13 
4 6 10 
5 6 0 
5 7 0 
5 8 0 
6 9 11 
8 9 0

样例输出 2

48

说明

第一个样例中道路和城市的布局。铺设好的道路以粗线显示。

对于 Mirko 和 Slavko 来说，有五条可能的路线。如果封锁道路 1-3、3-5 和 2-5，那么 Mirko 和 Slavko 就无法使用这五条路线中的任何一条。封锁这三条道路的代价是 5。

也可以只封锁两条道路 2-4 和 2-5，但这会导致更高的代价 6。