题目描述

曹操在赤壁之战中被诸葛亮和周瑜击败，但他并未放弃。由于曹军仍然不擅长水战，他想出了另一个办法：在长江上建造许多岛屿，借助这些岛屿，曹军可以轻松地进攻周瑜的部队。曹操还建造了连接岛屿的桥梁。如果所有岛屿都通过桥梁相连，曹军就能在这些岛屿之间灵活部署。周瑜无法容忍这一点，因此他想摧毁一些桥梁，使至少一个岛屿与其他岛屿分离。但周瑜只剩下一枚诸葛亮留下的炸弹，因此他只能摧毁一座桥梁。周瑜必须派遣携带炸弹的士兵去摧毁桥梁，而桥梁上可能有守卫。轰炸部队的士兵数量不能少于桥梁上的守卫数量，否则任务将失败。请计算周瑜完成岛屿分割任务至少需要派遣多少士兵。

输入格式

输入的测试数据有多组
每组的第一行包含两个正整数$n$和$m$,表示岛屿的数量和桥梁的数量，岛屿的编号分别为$1 \to n(2 \le n \le 1000,1 \le m \le n^2)$。
接下来$m$行表示$m$坐桥梁，每行包括三个整数$u,v,w$.表示一座链接岛屿$u$和$v$的桥梁，桥上有$w$名守卫

输出格式

对于每组阳历，输出完成任务需要最小的士兵的数量，如果无法完成任务，则输出-1

3 3  
1 2 7  
2 3 4  
3 1 4  
3 2  
1 2 7  
2 3 4

-1
4