题目描述

快递员小明的快递站位于城市的节点 $1$。他需要把 $n-1$ 件包裹分别送到节点 $2$ 到节点 $n$。城市中有 $m$ 条单行道，每条路连接两个节点并有一个通行时间。小明每次只能携带一件包裹，并且送完每件包裹后必须返回快递站。请计算小明送完所有包裹并最终回到快递站所需的最少总时间。

输入格式

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

接下来 $m$ 行，每行三个整数 $u, v, w$，表示存在一条从节点 $u$ 到节点 $v$、通行时间为 $w$ 的单行道。

输出格式

输出仅一行，包含一个整数，表示所需的最少总时间。

样例

5 10
2 3 5
1 5 5
3 5 6
1 2 8
1 3 8
5 3 4
4 1 8
4 5 3
3 5 6
5 4 2

83

提示

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

对于 $100\%$ 的数据，$1 \leq n \leq 10^3$，$1 \leq m \leq 10^5$，$1 \leq u, v \leq n$，$1 \leq w \leq 10^4$，输入保证任意两点之间互相可达。