Quốc gia Fermand có tổng cộng ~n~ hòn đảo được đánh số từ ~1~ đến ~n~. Các đảo được nối với nhau thông qua ~m~ tuyến đường vượt biển được đánh số từ ~1~ đến ~m~, tuyến đường hai chiều thứ ~i~ nối giữa hai đảo ~u_i~ và ~v_i~ với thời gian di chuyển ~t_i~. Giữa hai hòn đảo có thể có nhiều hơn một tuyến đường nối giữa chúng. Xuất phát từ một đảo bất kỳ có thể đi đến tất cả các đảo khác thông qua một hoặc nhiều tuyến đường.

Cho ~q~ truy vấn, mỗi truy vấn bao gồm ~k~ tuyến đường ~r_1,r_2,...,r_k~, yêu cầu xác định thời gian ít nhất để xuất phát từ đảo ~1~ di chuyển đến đảo ~n~ và đi qua mỗi tuyến đường trong ~k~ tuyến đường đã cho ít nhất một lần.

Input

• Dòng đầu tiên chứa hai số nguyên ~n~ và ~m~ ~(2 \le n \le 400~ ~;~ ~n-1 \le m \le 2 \times 10^5)~.
• ~m~ dòng tiếp theo, dòng thứ ~i~ chứa ba số nguyên ~u_i,v_i~ và ~t_i~ ~(1 \le u_i<v_i \le n~ ~;~ ~1 \le t_i \le 10^9)~.
• Dòng tiếp theo chứa số nguyên ~q~ ~(1 \le q \le 3000)~.
• ~q~ truy vấn được mô tả theo dạng sau: Dòng đầu tiên chứa số nguyên ~k~ ~(1 \le k \le 5)~, dòng thứ hai chứa ~k~ số nguyên ~r_1,r_2,...,r_k~ ~(1 \le r_1<r_2<...<r_k \le m)~.
• Dữ liệu đảm bảo có thể di chuyển giữa hai đảo bất kỳ thông qua một hoặc nhiều tuyến đường.

Output

• Với mỗi truy vấn, in ra trên một dòng là thời gian ít nhất để di chuyển từ đảo ~1~ đến đảo ~n~ sao cho đi qua mỗi tuyến đường trong ~k~ tuyến đường đã cho ít nhất một lần.

Examples

Sample Input 1

3 5
1 2 20
1 3 40
1 3 60
2 3 30
2 3 50
2
2
3 5
1
1

Sample Output 1

140
50

Sample Input 2

3 3
1 2 10
2 3 10
1 3 10
1
3
1 2 3

Sample Output 2

40

Notes

Trong ví dụ thứ nhất, ở truy vấn đầu tiên, yêu cầu phải đi qua các tuyến đường thứ ~3~ và thứ ~5~ ít nhất một lần. Cách di chuyển tối ưu như sau:

• Di chuyển từ đảo ~1~ đến đảo ~3~ thông qua tuyến đường thứ ~3~ với thời gian ~60~.
• Di chuyển từ đảo ~3~ đến đảo ~2~ thông qua tuyến đường thứ ~5~ với thời gian ~50~.
• Di chuyển từ đảo ~2~ đến đảo ~3~ thông qua tuyến đường thứ ~4~ với thời gian ~30~.

Tổng thời gian di chuyển là ~60+50+30=140~.