[ARC078D] Mole and Abandoned Mine

题意翻译

题目大意: 给一个n个点m条边的无向连通图(不存在自环或重边),每条边有一个边权,要求割掉若干条边,使1到n只有1条路径(不经过重复点),问割掉的边权和最小是多少。 感谢@sunyufei 提供的翻译

题目描述

[problemUrl]: https://arc078.contest.atcoder.jp/tasks/arc078_d モグラは $ 1 $ から $ N $ の番号がついた $ N $ 個の頂点と $ M $ 本の辺からなる単純連結無向グラフで表されるような廃坑に住むことにしました。 $ i $ 番目の辺は頂点 $ a_i $ と $ b_i $ をつないでおり、取り除くために $ c_i $ 円かかります。 モグラはいくつかの辺を取り除いて、頂点 $ 1 $ から頂点 $ N $ へ同じ頂点を $ 2 $ 回以上訪れないように移動する経路がただ $ 1 $ 通りのみ存在するようにしたいです。これを達成するために必要な資金の最小値を求めなさい。

输入输出格式

输入格式


Input is given from Standard Input in the following format: ``` $ N $ $ M $ $ a_1 $ $ b_1 $ $ c_1 $ $ : $ $ a_M $ $ b_M $ $ c_M $ ```

输出格式


Print the answer.

输入输出样例

输入样例 #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 1
1 2 1

输出样例 #2

0

输入样例 #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

输入样例 #4

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

输出样例 #4

200

输入样例 #5

2 1
1 2 1

输出样例 #5

0

输入样例 #6

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

输出样例 #6

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} $ - 与えられるグラフに多重辺や自己ループは存在しない - 与えられるグラフは連結 ### Problem Statement Mole decided to live in an abandoned mine. The structure of the mine is represented by a simple connected undirected graph which consists of $ N $ vertices numbered $ 1 $ through $ N $ and $ M $ edges. The $ i $ -th edge connects Vertices $ a_i $ and $ b_i $ , and it costs $ c_i $ yen (the currency of Japan) to remove it. Mole would like to remove some of the edges so that there is exactly one path from Vertex $ 1 $ to Vertex $ N $ that does not visit the same vertex more than once. Find the minimum budget needed to achieve this. ### Constraints - $ 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} $ - There are neither multiple edges nor self-loops in the given graph. - The given graph is connected. ### Sample Explanation 1 以下の図において、赤い破線で表されている辺は取り除かれた辺です。以下の図のように $ 2 $ つの辺を取り除くことで $ 200 $ 円で達成することが可能です。 ![45c15676bb602ca3b762561fc014ecd0.png](https://cdn.luogu.com.cn/upload/vjudge_pic/AT2657/0ba00f4bd99dcb47a2fb04015a84df5e9da99031.png) ### Sample Explanation 2 はじめから、頂点 $ 1 $ から頂点 $ N $ へのパスが $ 1 $ 通りしかないこともあります。 ### Sample Explanation 4 By removing the two edges represented by the red dotted lines in the figure below, the objective can be achieved for a cost of $ 200 $ yen. ![45c15676bb602ca3b762561fc014ecd0.png](https://cdn.luogu.com.cn/upload/vjudge_pic/AT2657/0ba00f4bd99dcb47a2fb04015a84df5e9da99031.png) ### Sample Explanation 5 It is possible that there is already only one path from Vertex $ 1 $ to Vertex $ N $ in the beginning.