题目描述

你是一位魔法学院的学徒，面前摆着 $N$ 张神秘的魔法符文卡。每张卡片背面刻有一个隐藏的魔力值：$1$ 或 $2$。

学院的水晶球已经揭示了 $M$ 条古老的预言。第 $i$ 条预言指出：

当编号为 $X_i$ 和编号为 $Y_i$ 的两张卡片的魔力值之和，加上古老常数 $Z_i$ 时，结果必定为偶数。

你需要完全解读所有卡片的魔力值。作为魔法师，你可以消耗 $1$ 点魔力 发动一次 “透视术”，直接看穿一张卡片的魔力。

在已知预言的前提下，你最少需要消耗多少魔力发动 “透视术”，才能确保推断出所有卡片的魔力值？

输入格式

第一行两个整数 $N,\ M$，分别表示魔法符文卡的数量和预言的数量。

接下来 $M$ 行，每行三个整数 $X_i,\ Y_i\ Z_i$，表示一条预言的内容。

输出格式

一个整数，表示最少需要消耗多少魔力发动 “透视术”，才能确保推断出所有卡片的魔力值。

样例

3 1
1 2 1

2

6 5
1 2 1
2 3 2
1 3 3
4 5 4
5 6 5

2

100000 1
1 100000 100

99999

样例1解释

对第 $1$ 张和第 $3$ 张卡片各使用一次 “透视术”，就可以确定所有卡片的魔力值。

数据范围

对于 $40\%$ 的数据，$2\le N\le 20$，$1\le M\le 20$。

对于 $100\%$ 的数据，$2\le N\le 10^5$，$1\le M\le 10^5$，$1\le X_i<Y_i\le N$，$1\le Z_i\le 100$，$(X_i,\ Y_i)$ 的组合互不相同。保证输入合法，无矛盾。