该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

やり残した鼓動がこの夜を覆って

零帧起手

题目描述

以放学后茶会为首的 $n$ 支乐队将在名为「CiRCLE」的 LiveHouse 开展名为 LoveLive! 的竞演大赛，优

胜者将会成为「Top Star」——让“喜欢”的炽热情感如光一般充满世界的闪耀路标！

LoveLive! 大赛共有 $m$ 场竞演，参与第$i$场竞演$(1 ≤ i ≤ m)$的两支乐队的编号为 $u_i$ 和 $v_i$ ，并且

该场竞演的主题为 $c_i (c_i = 0 \ or\ 1)$。

“「Top Star」产生的瞬间，奇迹与闪耀融合引发的化学反应，永远的光辉、一瞬的燃烧，谁都无法预测

的命运之舞台”——观众们就是想看到这个，因此，他们希望这 $m$ 场竞演的主题完全相同。

为了满足观众们的愿望，后藤一里——我们的神，决定降下她的神谕：

神每次可以选择一支乐队下达神谕，随后该支乐队会修改她们参与的每一场竞演的主题（若原来的

主题$c_i$ = 0，则修改为 1，反之亦然）。

神不喜多言（其实是社恐），所以希望降下的神谕尽可能少；神不屑计算（其实是学渣），所以请你

——「CiRCLE」的一名新手工作人员，为神计算出：

最少需要降下多少条神谕，才能使这 $m$ 场竞演的主题完全相同。

输入格式

第一行两个正整数 $n\ m$ ，分别表示乐队支数与竞演场数；

接下来的$m$行中，第$i$行的三个整数 $u_i, v_i, c_i$ ，表示参与该场竞演的两支乐队的编号和该场竞演的主题

$(1 ≤ u_i, v_i ≤ n, u_i \neq v_i, c_i = 0 \ or \ 1)$；

输出格式

一行一个整数，表示最少降下多少条神谕；若无法使这 $m$ 场竞演的主题完全相同，请输出 $−1$，表示神会亲自出手。

样例

3 3
1 2 1
3 2 1
3 1 0

1

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

2

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

-1

样例1：对2号乐队降下神谕，前两场竞演的主题变为0，三场竞演的主题完全相同；

样例2：对3、4号乐队降下神谕即可。

数据范围

任意两场竞演，参演的乐队不会完全相同。

对于$30\%$的数据，$1 ≤ n, m ≤ 20$；

对于$60\%$的数据，$1 ≤ n, m ≤ 1000$；

对于$100\%$的数据，$1 ≤ n, m ≤ 100000, m ≤ \frac{n(n-1)}{2}$；