人活着系列之Streetlights

Time Limit: 1000 ms Memory Limit: 65536 KiB

Problem Description

人活着如果是为了家庭,亲情----可以说是在这个世界上最温暖人心的,也是最让人放不下的,也是我在思索这个问题最说服自己接受的答案。对,也许活着是一种责任,为了繁殖下一代,为了孝敬父母,男人要养家糊口,女人要生儿育女,就这样循环的过下去,但最终呢?还是劳苦愁烦,转眼成空呀!
  为了响应政府节约能源的政策,某市要对路灯进行改革,已知该市有n个城镇,有m条道路,改革后该市只开一部分道路的路灯,而且要使任意两个城镇之间有路灯开着。城镇编号为0~n-1;每条道路开的路灯要花费一定的费用,求改革后最多能节省多少费用。

Input

 多组输入,每组第一行输入n, m(1≤n≤ 100000,n-1≤m ≤100000);接下来m行,每行3个数u, v, w;代表城镇u到城镇v开着路灯的花费为w。

Output

  输出改革后最多能节省的费用,如果数据不能保证任意两个城镇有路灯开着,输出-1。

Sample Input

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

Sample Output

5
-1

Hint

 

Source

xj