P6574纸牌杀游戏 | |
|
问题描述
南渝中学同学们之间流行一个纸牌杀的游戏,游戏开始有$N$张扑克牌$A_1,A_2,\cdots,A_N$,并且面都朝下,每张上写着1或者2,玩家的任务就是准确无误猜出所有扑克牌的数字,即为过关。当然游戏会给玩家提供$M$条信息。信息的形式如下:$A_{X_i}+A_{Y_i}+Z_i$的结果是偶数$(i=1,2,\cdots,M)$。不过,你也可以选择充值买道具,道具1元1个,道具一次只能查看一张牌的数字,用后即废。请问玩这局游戏至少需要充值多少才能过关?一些限制条件如下:
- 输入的值都是整数
- $2 \leq N \leq 10^5$
- $1 \leq M \leq 10^5$
- $1 \leq X_i < Y_i \leq N$
- $1 \leq Z_i \leq 100$
- $(X_i,Y_i)$这对数据不会重复出现
- 输入都是有效的,即一定可以找到一组数字$A_1,A_2,\cdot,A_N$满足条件。
输入格式
第一行,两个整数$N$和$M$。接下来$M$行,每行3个整数$X_i$ \(Y_i\) $Z_i$表示信息。格式如下:
\(N\) \(M\)
\(X_1\) \(Y_1\) \(Z_1\)
\(X_2\) \(Y_2\) \(Z_2\)
\(\vdots\)
\(X_M\) \(Y_M\) \(Z_M\)
输出格式
输出一个整数表示至少需要充多少钱。
样例输入 1
3 1
1 2 1
样例输出 1
2
样例输入 2
6 5
1 2 1
2 3 2
1 3 3
4 5 4
5 6 5
样例输出 2
2