最小斯坦纳树

【题目描述】

给定一个有 $N$ 个顶点和 $M$ 条边的连通无向图。第 $i$ 条边（$0 \le i < M$）连接顶点 $U_i$ 和 $V_i$，权值为 $W_i$。

此外，给定 $V(G)$ 的一个子集 $X = \{X_0, X_1, \ldots, X_{K - 1}\}$。请在 $G$ 的所有使 $X$ 中的顶点两两连通的子图中，找出边权和最小的一个。

【输入】

$N$ $M$
$U_0$ $V_0$ $W_0$
$U_1$ $V_1$ $W_1$
:
$U_{M - 1}$ $V_{M - 1}$ $W_{M - 1}$
$K$
$X_0$ $X_1$ ... $X_{K - 1}$

【输出】

$Y$ $Z$
$i_0$ $i_1$ ... $i_{Z - 1}$

$Y$ 是所选子图中边的权值之和，$Z$ 是所选边的数量。$i_0, i_1, \ldots, i_{Z - 1}$ 是所选子图中的边的编号。 如果有多个正确输出，输出其中任意一个。

【输入样例】

6 11
0 1 2
0 2 1
1 2 2
1 3 2
1 4 2
3 4 2
2 4 2
2 5 1
4 5 2
0 3 1
0 5 3
3
0 3 5

【输出样例】

3 3
1 7 9

【输入样例2】

1 1
0 0 1
1
0

【输出样例2】

0 0

【输入样例3】

5 11
0 1 1
0 1 10
0 2 100
0 3 1000
0 4 10000
1 2 10
1 3 1
1 4 100
2 3 10
2 4 1
3 4 1
3
1 3 4

【输出样例3】

2 2
6 10

【数据范围】

• $1 \leq N \leq 100$
• $N - 1 \leq M \leq 1000$
• $0 \leq U_i, V_i < N$
• $1 \leq W_i \leq 1000000000$
• $1 \leq K \leq \min(N, 12)$
• $0 \leq X_0 < X_1 < \ldots < X_{K - 1} < N$
• 给定的图是连通的。

【来源】

Library Checker（yosupo06） minimum_steiner_tree

本题为 special judge（输出任意合法解），暂不可本地评测。