芙宁娜与胡桃一起，她们打算到n个景点游玩，分别为每个景点编号为1, 2, . . . , n。

打开地图，她们发现有m条道路，每条道路连接了两个景点，道路双向均可通行。因为正值海灯节，所以每条道路都推出专门的通行优惠卡——每条道路只需要在第一次通行时购买优惠卡，此后再次来到这条道路可凭借优惠卡免费通行。

芙宁娜和胡桃希望用最少的路费就游览完所有的景点，请你告诉他们最便宜的花费是多少。

第一行包含两个整数n, m(2≤n≤1000, 1≤m≤) ，具体含义见题面。

接下来m行，每行包含三个整数u, v, w(1≤u < v≤n, 1≤w≤1000) ，表示从u号景点到v号景点的通行优惠卡的价格为w，保证输入没有自环、重边。

如果没有路线可以到达，一行中输出-1。

否则，一行中输出一个整数，表示最便宜的花费。