103694: [Atcoder]ABC369 E - Sightseeing Tour

Problem Statement

There are $N$ islands and $M$ bidirectional bridges connecting two islands. The islands and bridges are numbered $1$, $2$, $\ldots$, $N$ and $1$, $2$, $\ldots$, $M$, respectively.
Bridge $i$ connects islands $U_i$ and $V_i$, and the time it takes to cross it in either direction is $T_i$.
No bridge connects an island to itself, but it is possible for two islands to be directly connected by more than one bridge.
One can travel between any two islands using some bridges.

You are given $Q$ queries, so answer each of them. The $i$-th query is as follows:

You are given $K_i$ distinct bridges: bridges $B_{i,1}, B_{i,2}, \ldots, B_{i,K_i}$.
Find the minimum time required to travel from island $1$ to island $N$ using each of these bridges at least once.
Only consider the time spent crossing bridges.
You can cross the given bridges in any order and in any direction.

Constraints

• $2 \leq N \leq 400$
• $N-1 \leq M \leq 2 \times 10^5$
• $1 \leq U_i < V_i \leq N$
• $1 \leq T_i \leq 10^9$
• $1 \leq Q \leq 3000$
• $1 \leq K_i \leq 5$
• $1 \leq B_{i,1} < B_{i,2} < \cdots < B_{i,K_i} \leq M$
• All input values are integers.
• It is possible to travel between any two islands using some bridges.

Input

The input is given from Standard Input in the following format:

$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}}$

Output

Print $Q$ lines. The $i$-th line ($1 \leq i \leq Q$) should contain the answer to the $i$-th query as an integer.

Sample Input 1

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

Sample Output 1

25
70

For the first query, we need to find the minimum time to travel from island $1$ to island $3$ while using bridge $1$. The minimum time is achieved by using bridge $1$ to move from island $1$ to island $2$, then using bridge $4$ to move from island $2$ to island $3$. The time taken is $10 + 15 = 25$. Hence, print $25$ on the first line.

For the second query, we need to find the minimum time to travel from island $1$ to island $3$ while using both bridges $3$ and $5$. The minimum time is achieved by using bridge $3$ to move from island $1$ to island $3$, then using bridge $5$ to move to island $2$, and finally using bridge $4$ to return to island $3$. The time taken is $30 + 25 + 15 = 70$. Hence, print $70$ on the second line.

Sample Input 2

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

Sample Output 2

5
3

For each query, you can cross the specified bridges in either direction.

Sample Input 3

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

Sample Output 3

4000000000

Beware that the answer may not fit in a $32$-bit integer.

问题陈述

有$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$旅行的最小时间。
只考虑过桥的时间。
你可以以任何顺序和方向过给定的桥梁。

约束条件

• $2 \leq N \leq 400$
• $N-1 \leq M \leq 2 \times 10^5$
• $1 \leq U_i < V_i \leq N$
• $1 \leq T_i \leq 10^9$
• $1 \leq Q \leq 3000$
• $1 \leq K_i \leq 5$
• $1 \leq B_{i,1} < B_{i,2} < \cdots < B_{i,K_i} \leq M$
• 所有输入值都是整数。
• 可以通过某些桥梁在任意两个岛屿之间旅行。

输入

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

$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 \leq i \leq Q$）应包含第$i$个查询的答案作为整数。

示例输入1

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

示例输出1

25
70

对于第一个查询，我们需要找出使用桥梁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。

示例输入2

6 6
1