有一个快递员要送件，配送站在节点 1 。他总共要送 n-1 个物品，其目的地分别是节点 2 到节点 n 。共有 m 条双向道路。这个快递员每次只能带一样物品，并且运送每件物品过后必须返回配送站。求送完这 n-1 样东西并且最终回到配送站最少需要的时间。

（1\leq n \leq 10000,1\leq m \leq 100000 ）

第一行包括两个整数，n 和m ，表示城市的节点数量和道路数量。

第二行到第 m+1 行，每行三个整数， u,v,w ，表示从 u到 v 有一条通过时间为 w 的道路。

输出仅一行，包含一个整数，为最少需要的时间。

对于 30\%的数据，1\leq n \leq200 。

对于 100\%的数据，1\leq n \leq10000 。1\leq u, v \leq10000,1\leq w \leq10000输入保证任意两点都能互相到达。

样例说明：

需要走两遍，这点不要忘记；