← 返回题目列表

AtCoder · arc078_d

F. 鼹鼠和废弃矿井

中文机器翻译题面 查看原题

分数: 900 点

问题陈述

鼹鼠决定住在一个废弃的矿井里。矿井的结构由一个简单的连通无向图表示,其中包括 N 顶点编号 1 通过 N 和 M 边缘。 的 i第一条边连接顶点 a_i 和 b_i,并且成本 c_i 日元(日本货币)将其删除。

Mole 希望删除一些边缘,以便从 Vertex 出发只有一条路径 1 到顶点 N 不会多次访问同一顶点。找出实现这一目标所需的最低预算。

约束

  • 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}
  • 给定图中既没有重边,也没有自环。
  • 给定的图形已连接。

输入

输入由标准输入按以下格式给出:

N M
a_1 b_1 c_1
:
a_M b_M c_M

输出

打印答案。


示例输入 1

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

示例输出 1

200

通过去除下图中红色虚线代表的两条边,可以达到目的,成本为 200 日元。

45c15676bb602ca3b762561fc014ecd0.png

示例输入 2

2 1
1 2 1

示例输出 2

0

从 Vertex 出发可能已经只有一条路径 1 到顶点 N 开头。


示例输入 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