题目描述

一个送餐员，要骑车从家出发，给n-1个顾客送餐，然后返回家。

下面的示例地图中，每个圆圈代表一个地方，1是送餐员的家，2~n是顾客所在地。连接两个圆圈的线表示路，线上面的数字是行驶这段路所需时间。路都可以双向行驶。

请你帮送餐员设计一条线路，使他用最短时间完成送餐任务并返回家，每个地点只去一次。输出这个最短的时间。

输入格式

第1行有2个整数n和m，代表有n个点（包括1号点），m条边(n≤20，m≤200)；

接下来m行，每行3个整数x，y，w，代表x到y之间存在一有长度为w的路。

输出格式

输出送餐员所需的最短时间。

输入/输出样例

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

27

样例解释

最优路线1-2-4-5-3-1，需要时间5+3+4+9+6=27。

说明/提示

时间1000ms，内存256MiB