俺的图图呢

题号：NC231655
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

你有一个 $n$ 个点 $m$ 条边的带权无向图 $G=<V,E>$ （不一定连通），现在有 $k$ 个关键点 $s_1,s_2,\cdots,s_k$ ，请设计一种方案，将这些点分成若干个大小大于 $1$ 的集合 $S_i$ ，且任意一个关键点至少要在某一个集合中，那么可以定义集合 $S_i$ 的价值：

1. 将 $S_i$ 中的所有元素按某一方式排列得到序列 $\{P_j\}$ .
2. 对于 $P_j$ 和 $P_{j+1}(j<|S_i|)$ ，需要在原图中找到一条从 $P_{j}$ 到 $P_{j + 1}$ 的**简单路径**（即不经过重复点的路径），同时也要找一条从 $P_{|S_i|}$ 到 $P_1$ 的简单路径，并记录路径上每条边的经过次数。
3. 集合 $S_i$ 的价值 $val_i$ 为 $\sum\limits_{e \in E} w_e * [经过这条边的次数为奇数]$ （ $w_e$ 为该边边权，即经过这条边奇数次，其贡献为 $w_e$ ，否则为 $0$ ）。

如果这种方案划分出了 $x$ 个集合，那么该方案的花费是 $x + \sum\limits_{i=1}^x val_i$ .

求花费最小的方案的花费。

保证这 $k$ 个关键点中，每一个点至少可以通向另外一个点。

输入描述:

第一行三个整数，含义如题面所述。
第二行个整数，表示个关键点。
接下来行，每行三个整数，表示一条在结点和之间，边权为的无向边。
（，没有自环和重边）

输出描述:

一个整数，即题目中所求的最小花费。

示例1

输入

复制

8 7 6
1 5 4 6 8 7
2 5 3
1 4 4
5 3 1
6 3 8
3 7 5
2 8 9
2 3 6

输出

复制

说明


可分成两个集合.在集合中，可以构造序列，选择路径，这样每条边都走了两次，因此；在集合中，构造序列，选择路径，这样这条边也走了两次，因此.那么答案就是，可以证明，这是所求的最小值。