Description

求居润国是否能在上述条件要求下无伤通过最后一关。如果可以，输出居润国控制的以撒最少所需的血量 $B$，否则输出 'IMP0SSBLE!!'

Input Format

第一行有五个数，分别为 $n,m,s,t,k$，分别表示一共有 $n$ 个房间，以及 $m$ 对相邻房间及其通过所需要的血量，以 $s$ 为起点，$t$ 为终点，要在 $k$ 时刻恰好走到终点。

接下来 $m$ 行每行分别有三个数，分别是 $u,v,w$，表示房间 $u$ 和房间 $v$ 相邻，两个房间互相通过的血量均为 $w$。

接下来一行是单独的一个数 $a$，表示一共有 $a$ 只怪物

接下来有 $a$ 个数据分别表示每个怪物的游走规律

每个数据的第一个数 $T$ 表示怪物游走的房间个数，接下来有 $T$ 个房间编号表示从第零时刻开始怪物将从第一个房间按顺序和周期游走。

Output Format

仅一行，居润国控制以撒的最少所需血量 $B$，或是 'IMP0SSBLE!!'

2 1 1 2 1
1 2 1
0

1

2 1 1 2 1
1 2 2
0

2

2 1 1 2 10000001
1 2 2
0

2

2 1 1 2 10000001
1 2 2
1
2
2 1

2

Hint

共 $20$ 组数据。

对于 $15\%$ 的数据，$a = 0$，$k \leq 20$。

对于 $25\%$ 的数据，$a \leq 3$，$k \leq 1500$。

对于 $50\%$ 的数据，$a \leq 3$，$k \leq 10^4$。

对于 $70\%$ 的数据，$a \leq 20$，$k \leq 10^6$。

对于 $85\%$ 的数据，$a \leq 30$，$k \leq 10^8$。

对于 $100\%$ 的数据，$a \leq 30$，$k \leq 2*10^9$，$2 \leq T \leq 4$，$n \leq 50$，$m \leq 1250$。

所有输入皆在 int 范围内。

所有数据皆大于零，可能会有重边，若一条边输入多次 则以最后一次出现的权值为准。