A75068.观光旅游

有 $N$ 座岛屿和 $M$ 条双向桥梁，每条桥梁连接两个岛屿。岛屿和桥梁分别编号为 $1,2,\cdots,N$ 和 $1,2,\cdots,M$。
桥梁 $i$ 连接岛屿 $U_i$ 和 $V_i$ ，在任一方向上穿过它所需的时间是 $T_i$ 。
没有桥梁会连接同一个岛屿，但两个岛屿可以通过多座桥梁直接连接。
人们可以使用一些桥梁在任意两个岛屿之间旅行。

您会收到 $Q$ 的查询，请逐一回答。第 $i$ 个查询如下：

你会得到 $K_i$ 不同的桥：桥 $B_{i,1},B_{i,2},\cdots,B_{i,K_i}$。
找到使用这些桥梁从 $1$ 岛屿到 $N$ 岛屿至少一次所需的最短时间。
只考虑过桥所花费的时间。
你可以以任何顺序和任何方向穿过给定的桥梁。

第一行输入两个正整数 $N,M$ $(2 \leq N \leq 400;N-1 \leq M \leq 2 \times 10^5)$ ，表示岛屿个数。

接下来 $M$ 行，每行输入三个整数 $U,V,T$ $(1 \leq U_i \lt V_i \leq N;1 \leq T_i \leq 10^9)$ ，表示这条桥梁连接的两个岛屿以及通过这条桥梁需要花费的时间。

第 $M+1$ 行输入一个正整数 $Q$ $(1 \leq Q \leq 3000)$ ，表示询问次数。

接下来 $Q$ 个询问，每个询问输入两行：

第一行输入一个正整数 $K$ $(1 \leq K_i \leq 5)$，表示这次询问需要通过的桥梁个数。

第二行输入 $K$ 个正整数 $B_1,B_2,\cdots,B_k$ $(1 \leq B_1 \lt B_2 \lt \cdots \lt B_K \leq M)$，表示这次询问需要通过的桥梁的编号。

输出 $Q$ 行，每行一个整数。

第 $i$ 个整数表示第 $i$ 次询问的答案。

样例1解释

对于第一个查询，我们需要找到通过桥梁 $1$ 从岛屿 $1$ 到岛屿 $3$ 的最短时间。最短时间是通过桥梁 $1$ 从岛屿 $1$ 到岛屿 $2$，然后通过桥梁 $4$ 从岛屿 $2$ 移动到岛屿 $3$ 来实现的。所需时间为 $10+15=25$。因此，在第一行输出 $25$。

对于第二个查询，我们需要找到通过桥梁 $3$ 和桥梁 $5$ 从岛屿
$1$ 到岛屿 $3$ 的最短时间。最短时间是通过桥梁 $3$ 从岛 $1$ 移动到岛 $3$ ，然后通过桥梁 $5$ 移动到岛屿 $2$ ，最后通过桥梁 $4$ 返回岛屿 $3$ 来实现的。所需时间为 $30+25+15=70$。因此，在第二行输出 $70$。