放他去修仙是一款特别好玩的武侠修仙游戏，秘境探索是游戏的一大特色。 随着修行者能力的提升，玩家也可以不断的探索新的奇山怪景，直至探索人人都向往的天外天。如今天地灵气聚集，无需自身修为即可自由出入各大仙境。 小G作为游戏的忠实玩家，非常期待去探索所有的地方，虽然没有了仙法的限制，但是每一条路都需要消耗一定的机缘。 小G为了尽量少的消耗机缘，每一个地点至多经过俩次。那么要游览所有的地点，至少需要多少机缘呢？

输入描述:

第一行n,m。n(1接下来有m行,每行有a,b,c(1=a,b=n ; 1=c=100), 代表了仙境a到达仙境b需要消耗c的机缘。

输出描述:

输出小G需要消耗的最小的机缘。如果无法游览所有的地点,输出-1。