#4331. JSOI2012 越狱老虎桥

内存限制:256 MiB 时间限制:10 Sec

题目描述

这里,是美丽的南京;这里,是秀美的进香河;这里是安逸的老虎桥。 
如果说进香河的美,美在其秀美的风光,倒不如说是美在了那惬意的南京古典小巷式生活。如果说进香河的迷人,在其淳朴的民风,倒不如说是那被历史掩埋了的秘密吸引着人们好奇的心。 
也许很多人都还记得,老虎桥监狱,北洋时期江南最大的监狱,在近一个世纪中,面对满清、北洋、民国、新中国几朝兴衰,名称屡次更替,沧桑尽显其中。 
现在的人们,恐怕很难相信,到底有多少惊心动魄的事情曾经就在这里上演。 
那是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。 


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