分数: 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 日元。
示例输入 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