题目背景

这是战火纷飞的2333年，世界被分为XC联盟和WJ联盟，两个联盟互相开火。

题目描述

这是战火纷飞的2333年，世界被分为XC联盟和WJ联盟，两个联盟互相开火。Q国总统ZR想到Yugo国进行十分紧急的国事访问，但不能坐飞机，只能坐车。由于路上有许多不同的国家而且有些无政府国，所以有许多路是坏的。路没有从自己通向自己的（作死吗。。。）。你需要确定一条具体的路线，并且由于WJ联盟的人随时可能过来，你需要把这条路线经过的所有城市周围的其他路都毁掉。你是上帝视角，你需要帮助ZR总统到达Yugo，你可以毁掉一些原本是好的路，也可以把坏的路修好，但不能新修路。给你一份地图，地图上，ZR国坐落在1城，Yugo首都在n城。帮助ZR总统尽快到达Yugo，你可以获得ZR总统在WJ联邦银行的30亿存款和1000万人的军队，和ZR总统一起瓜分地球（以上是诈骗内容。。。）。

输入格式

第一行，n，m，（2<=n<=1000,0<=m<=1000），n是Yugo首都，m是公路数量。

第2至m+1行，a，b，c，a是公路起始城市，b是公路结束城市，c是路的情况（1：能通行/0：不能通行）。

输出格式

第一行，k，需要改变路状态的最小数量。

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

3

提示

把 1 2 1 路径变成不可用

把 1 3 0 路径变成可用

把 2 3 1 路径变成不可用

即可