题目描述

モグラは $1$ から $N$ の番号がついた $N$ 個の頂点と $M$ 本の辺からなる単純連結無向グラフで表されるような廃坑に住むことにしました。 $i$ 番目の辺は頂点 $a_i$ と $b_i$ をつないでおり、取り除くために $c_i$ 円かかります。

モグラはいくつかの辺を取り除いて、頂点 $1$ から頂点 $N$ へ同じ頂点を $2$ 回以上訪れないように移動する経路がただ $1$ 通りのみ存在するようにしたいです。これを達成するために必要な資金の最小値を求めなさい。

输入格式

入力は以下の形式で標準入力から与えられる。

$N$ $M$ $a_1$ $b_1$ $c_1$ $:$ $a_M$ $b_M$ $c_M$

输出格式

答えを出力せよ。

题目大意

题目大意：

给一个n个点m条边的无向连通图（不存在自环或重边），每条边有一个边权，要求割掉若干条边，使1到n只有1条路径（不经过重复点），问割掉的边权和最小是多少。

感谢@sunyufei 提供的翻译

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

200

2 1
1 2 1

0

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

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}$
• 与えられるグラフに多重辺や自己ループは存在しない
• 与えられるグラフは連結

Sample Explanation 1

以下の図において、赤い破線で表されている辺は取り除かれた辺です。以下の図のように $2$ つの辺を取り除くことで $200$ 円で達成することが可能です。 

Sample Explanation 2

はじめから、頂点 $1$ から頂点 $N$ へのパスが $1$ 通りしかないこともあります。