최소 슈타이너 트리

정점이 $N$개이고 간선이 $M$개인 연결된 무방향 그래프가 주어진다. $i$번째 간선 $(0 \le i < M)$은 정점 $U_i$와 $V_i$를 연결하며 가중치는 $W_i$이다.

또한 $V(G)$의 부분집합 $X = \{X_0, X_1, \ldots, X_{K - 1}\}$가 주어진다. $X$의 정점들이 쌍마다 연결되어 있는 $G$의 부분 그래프 중에서 간선 가중치의 합이 최소인 것을 하나 구한다.

제약 조건

• $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 \le X_0 < X_1 < \ldots < X_{K - 1} < N$
• 주어진 그래프는 연결되어 있다.

$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}$는 선택한 부분 그래프에 포함된 간선들의 인덱스이다. 올바른 출력이 여러 개라면 그중 아무거나 출력한다.