题目背景

居润国迷上了一款游戏《以撒的结合重生》。他已经打到了最后一关，这一关有特殊的走位技巧。

1. 居润国从时刻 $0$ 开始，要控制以撒从起点走到终点。

2. 居润国只能在第 $k$ 时刻恰好走到终点。（从一个房间走到另一个房间居润国需要花费一个单位时间，居润国手速快，不会在同一个房间停留，以撒可以在这些房间中来回走动）

3. 若房间 $u$ 和 $v$ 相连，则居润国能控制以撒通过这两个房间的通道当且仅当以撒的血量大于等于 $f(u, v)$

4. 在这些房间之间有一堆怪物在游走。

5. 居润国为了求稳，于是上网找到了一个解码器，在代码中发现这些怪物们游走的房间有固定的规律：怪物每次都会从一个房间移动到另一个房间（也需花费一个单位时间），且他们总是在几个固定的房间按照固定的顺序内游走，游走的房间个数为 $T$。

为了不在玩游戏时失误，居润国希望能够避开所有的怪物走到终点，即无伤通过最后一关，同时希望你找到居润国控制的以撒完成这个任务至少需要的血量。对编程一窍不通的他找到了你，希望寻求解决。如果要是你无法解决，那么就光明正大地告诉他： 'IMP0SSBLE!!' 他一定不会打死你的。

题目描述

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

输入格式

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

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

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

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

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

输出格式

仅一行，居润国控制以撒的最少所需血量 $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

提示

共 $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 范围内。

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