F - Mole and Abandoned Mine Editorial /

Time Limit: 4 sec / Memory Limit: 256 MB

配点 : 900900

問題文

モグラは 11 から NN の番号がついた NN 個の頂点と MM 本の辺からなる単純連結無向グラフで表されるような廃坑に住むことにしました。 ii 番目の辺は頂点 aia_ibib_i をつないでおり、取り除くために cic_i 円かかります。

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

制約

  • 2N152 \leq N \leq 15
  • N1MN(N1)/2N-1 \leq M \leq N(N-1)/2
  • 1ai,biN1 \leq a_i, b_i \leq N
  • 1ci1061 \leq c_i \leq 10^{6}
  • 与えられるグラフに多重辺や自己ループは存在しない
  • 与えられるグラフは連結

入力

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

NN MM
a1a_1 b1b_1 c1c_1
::
aMa_M bMb_M cMc_M

出力

答えを出力せよ。


入力例 1Copy

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

出力例 1Copy

Copy
200

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

45c15676bb602ca3b762561fc014ecd0.png

入力例 2Copy

Copy
2 1
1 2 1

出力例 2Copy

Copy
0

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


入力例 3Copy

Copy
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

出力例 3Copy

Copy
133677

Score : 900900 points

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 NN vertices numbered 11 through NN and MM edges. The ii-th edge connects Vertices aia_i and bib_i, and it costs cic_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 11 to Vertex NN that does not visit the same vertex more than once. Find the minimum budget needed to achieve this.

Constraints

  • 2N152 \leq N \leq 15
  • N1MN(N1)/2N-1 \leq M \leq N(N-1)/2
  • 1ai,biN1 \leq a_i, b_i \leq N
  • 1ci1061 \leq c_i \leq 10^{6}
  • There are neither multiple edges nor self-loops in the given graph.
  • The given graph is connected.

Input

Input is given from Standard Input in the following format:

NN MM
a1a_1 b1b_1 c1c_1
::
aMa_M bMb_M cMc_M

Output

Print the answer.


Sample Input 1Copy

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

Sample Output 1Copy

Copy
200

By removing the two edges represented by the red dotted lines in the figure below, the objective can be achieved for a cost of 200200 yen.

45c15676bb602ca3b762561fc014ecd0.png

Sample Input 2Copy

Copy
2 1
1 2 1

Sample Output 2Copy

Copy
0

It is possible that there is already only one path from Vertex 11 to Vertex NN in the beginning.


Sample Input 3Copy

Copy
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

Sample Output 3Copy

Copy
133677


2025-02-26 (Wed)
14:56:24 +00:00