有 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，表示岛屿数量和桥的数量
接下来M行，三个数字，a,b,c分别表示从a到b需要c的时间
接下来一个数字Q，表示Q次查询
对于每次查询，首先是一个数字K，表示经过K座桥，然后是K座桥的编号！
Q个数字，表示每次查询通过的最短时间
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
5 5 1 2 1000000000 2 3 1000000000 3 4 1000000000 4 5 1000000000 1 5 1000000000 1 1 3
4000000000
- 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
- 所有输入值均为整数。
- 利用一些桥梁可以在任意两个岛屿之间旅行。
样例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 。