AT_arc078_d [ARC078F] Mole and Abandoned Mine

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

N/A

N/A

### 制約 - $ 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 $ 円で達成することが可能です。 !\[45c15676bb602ca3b762561fc014ecd0.png\](https://atcoder.jp/img/arc078/45c15676bb602ca3b762561fc014ecd0.png) ### Sample Explanation 2 はじめから、頂点 $ 1 $ から頂点 $ N $ へのパスが $ 1 $ 通りしかないこともあります。