芙宁娜与胡桃一起，她们打算到 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 。

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