P3821 Isaac

居润国迷上了一款游戏《以撒的结合重生》。他已经打到了最后一关，这一关有特殊的走位技巧。 1. 居润国从时刻 $0$ 开始，要控制以撒从起点走到终点。 2. 居润国只能在第 $k$ 时刻恰好走到终点。（从一个房间走到另一个房间居润国需要花费一个单位时间，居润国手速快，不会在同一个房间停留，以撒可以在这些房间中来回走动） 3. 若房间 $u$ 和 $v$ 相连，则居润国能控制以撒通过这两个房间的通道当且仅当以撒的血量大于等于 $f(u, v)$ 4. 在这些房间之间有一堆怪物在游走。 5. 居润国为了求稳，于是上网找到了一个解码器，在代码中发现这些怪物们游走的房间有固定的规律：怪物每次都会从一个房间移动到另一个房间（也需花费一个单位时间），且他们总是在几个固定的房间按照固定的顺序内游走，游走的房间个数为 $T$。 为了不在玩游戏时失误，居润国希望能够避开所有的怪物走到终点，即无伤通过最后一关，同时希望你找到居润国控制的以撒完成这个任务至少需要的血量。对编程一窍不通的他找到了你，希望寻求解决。如果要是你无法解决，那么就光明正大地告诉他： `'IMP0SSBLE!!'` 他一定不会打死你的。

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

无

无

共 $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 范围内。 所有数据皆大于零，**可能会有重边，若一条边输入多次 则以最后一次出现的权值为准。**