8331: BZOJ4331：JSOI2012 越狱老虎桥

这里，是美丽的南京；这里，是秀美的进香河；这里是安逸的老虎桥。  如果说进香河的美，美在其秀美的风光，倒不如说是美在了那惬意的南京古典小巷式生活。如果说进香河的迷人，在其淳朴的民风，倒不如说是那被历史掩埋了的秘密吸引着人们好奇的心。  也许很多人都还记得，老虎桥监狱，北洋时期江南最大的监狱，在近一个世纪中，面对满清、北洋、民国、新中国几朝兴衰，名称屡次更替，沧桑尽显其中。  现在的人们，恐怕很难相信，到底有多少惊心动魄的事情曾经就在这里上演。  那是1948年的冬天，南京地下组织的一支小分队决定偷袭老虎桥监狱，救出被困的数百名人员。那时的老虎桥监狱，被N层电网围了起来，由内而外，依次编号为1,2,…,N。第1层电网接有高压电。有M条高压线，连接了所有电网，其中第i条高压线连接了第ai和bi层电网，如果要破坏第i条高压线，需要至少动用Ti位特工。面对这么多层电网，偷袭小分队犯愁了。至少需要破坏一层电网，否则是无法偷袭成功的。  然而，狡猾的间谍却知道了这件事情，为了破坏偷袭计划，敌人秘密地又增加了一条高压线，不让偷袭小分队的成员发现。  为了能够偷袭成功，不论新增的这一条秘密高压线是连接哪两层电网的，小分队都必须要破坏且仅破坏一条高压线，使得至少有一层电网不通电。注意，对于新增的高压线，我们并不知道需要多少位特工才能成功破坏。现在的问题是，偷袭小分队至少需要多少名特工呢？  决战就在今夜！ 

输入格式

第一行有2个整数，N和M，分别表示电网层数和高压线个数。  之后M行，每行3个整数，分别是ai, bi和Ti。 

输出格式

输出只有一行，包含一个整数，表示最少需要动用的特工人数。  如果计划必然失败，则输出 -1。 

样例输入

3 2 
1 2 1 
2 3 2 

样例输出

-1 

提示

对于100%的数据，N<=500000，M<=1000000，T<=100000。 

应上传者要求，此题不公开，如有异议，请提出.

题目来源

没有写明来源