题目描述

鼹鼠决定住在一个废弃矿井中，该矿井可以表示为一个包含编号为 $1$ 到 $N$ 的 $N$ 个顶点和 $M$ 条边的简单连通无向图。第 $i$ 条边连接顶点 $a_i$ 和 $b_i$，移除这条边需要 $c_i$ 日元。

鼹鼠希望通过移除一些边，使得从顶点 $1$ 到顶点 $N$ 的路径仅有一条，并且在路径上不经过同一个顶点两次。请计算实现这一目标所需的最小资金。

输入格式

输入以以下格式从标准输入中给出。

$N$ $M$
$a_1$ $b_1$ $c_1$
$\vdots$
$a_M$ $b_M$ $c_M$

输出格式

请输出答案。

输入输出样例 #1

输入 #1

4 6
1 2 100
3 1 100
2 4 100
4 3 100
1 4 100
3 2 100

输出 #1

200

输入输出样例 #2

输入 #2

2 1
1 2 1

输出 #2

0

输入输出样例 #3

输入 #3

15 22
8 13 33418
14 15 55849
7 10 15207
4 6 64328
6 9 86902
15 7 46978
8 14 53526
1 2 8720
14 12 37748
8 3 61543
6 5 32425
4 11 20932
3 12 55123
8 2 45333
9 12 77796
3 9 71922
12 15 70793
2 4 25485
11 6 1436
2 7 81563
7 11 97843
3 1 40491

输出 #3

133677

说明/提示

限制条件

• $2 \leq N \leq 15$
• $N-1 \leq M \leq N(N-1)/2$
• $1 \leq a_i, b_i \leq N$
• $1 \leq c_i \leq 10^6$
• 给定的图中不存在重边或自环
• 给定的图是连通图

样例解释 1

在下图中，用红色虚线表示被移除的边。按照该图的方式移除两条边，总共需要 $200$ 日元。

样例解释 2

有时从一开始，顶点 $1$ 到顶点 $N$ 的路径就只有一种。