观光游览

题目描述

有 $N$ 座岛屿和 $M$ 座连接两座岛屿的双向桥梁。岛屿和桥梁分别编号为 $1,2,\ldots,N$ 和 $1,2,\ldots,M$。

桥梁 $i$ 连接岛屿 $U_i$ 和 $V_i$，无论朝哪个方向，通过这座桥所需的时间均为 $T_i$。

没有桥梁连接岛屿自身，但两座岛屿之间可能存在多座桥。

可以借助若干桥梁在任意两座岛屿之间通行。

给定 $Q$ 个询问，请回答每一个。第 $i$ 个询问如下：

给定 $K_i$ 座互不相同的桥梁：桥梁 $B_{i,1}, B_{i,2}, \ldots, B_{i,K_i}$。

求从岛屿 $1$ 到岛屿 $N$、且每条给定桥梁至少经过一次所需的最短时间。

只考虑过桥所花的时间。

可以按任意顺序、沿任意方向穿过这些给定的桥梁。

输入格式

输入按以下格式从标准输入给出：

$N$ $M$
$U_1$ $V_1$ $T_1$
$U_2$ $V_2$ $T_2$
$\vdots$
$U_M$ $V_M$ $T_M$
$Q$
$K_1$
$B_{1,1}$ $B_{1,2}$ $\cdots$ $B_{1,{K_1}}$
$K_2$
$B_{2,1}$ $B_{2,2}$ $\cdots$ $B_{2,{K_2}}$
$\vdots$
$K_Q$
$B_{Q,1}$ $B_{Q,2}$ $\cdots$ $B_{Q,{K_Q}}$

输出格式

输出 $Q$ 行。第 $i$ 行 ($1 \le i \le Q$) 输出第 $i$ 个询问的答案（作为整数）。

样例

3 5
1 2 10
1 3 20
1 3 30
2 3 15
2 3 25
2
1
1
2
3 5

25
70

对于第一个询问，需要求从岛屿 $1$ 到岛屿 $3$、且必须使用桥梁 $1$ 的最短时间。 最短路径为：使用桥梁 $1$ 从岛屿 $1$ 到岛屿 $2$，再使用桥梁 $4$ 从岛屿 $2$ 到岛屿 $3$。时间为 $10 + 15 = 25$。 因此第一行输出 $25$。

对于第二个询问，需要求从岛屿 $1$ 到岛屿 $3$、且必须同时使用桥梁 $3$ 和 $5$ 的最短时间。 最短路径为：使用桥梁 $3$ 从岛屿 $1$ 到岛屿 $3$，再使用桥梁 $5$ 到岛屿 $2$，最后使用桥梁 $4$ 返回岛屿 $3$。时间为 $30 + 25 + 15 = 70$。 因此第二行输出 $70$。

6 6
1 5 1
2 5 1
2 4 1
3 4 1
3 6 1
1 6 1
2
5
1 2 3 4 5
1
5

5
3

对于每个询问，可以沿任意方向穿过指定的桥梁。

5 5
1 2 1000000000
2 3 1000000000
3 4 1000000000
4 5 1000000000
1 5 1000000000
1
1
3

4000000000

注意答案可能超出 $32$-bit 整数的范围。

数据范围

• $2 \le N \le 400$
• $N-1 \le M \le 2 \times 10^5$
• $1 \le U_i \lt V_i \le N$
• $1 \le T_i \le 10^9$
• $1 \le Q \le 3000$
• $1 \le K_i \le 5$
• $1 \le B_{i,1} \lt B_{i,2} \lt \cdots \lt B_{i,K_i} \le M$
• 所有输入值均为整数。
• 可以借助若干桥梁在任意两座岛屿之间通行。