题目描述

由于 fot 机房⾥⿊暗势⼒猖獗，善良的⼩ G 遭到了⾮⼈的折磨。现在，⼩ G 被扔到了⼀个地牢⾥，从时刻 $0$ 开始，要从起点 $S$ ⾛向终点 $T$——那是唯⼀通向外界的地⽅。⿊暗势⼒为了进出地牢，会在 $k$ 时刻开放终点，也仅会在 $k$ 时刻开放终点。

地牢有 $n$ 个房间，对于给定 $m$ 对 $(u,v)$ 的房间之间有⼀扇⻔，⻔当然是可以从任意⼀边进⼊，任意⼀边出来。每扇⻔有需要⼀定⼒量来推开，即只有⼒量⼤于这个值，才能通过这扇⻔。当然，通过⼀扇⻔需要 $1$ 时刻的时间，也即从第 $x$ 时刻到第 $x+1$ 时刻，⼩ G 能通过⼀扇⻔。

当然，毁灭世界的恶势⼒不会如此轻易的放过他，于是，他们⽤⾼超的 OI 技术编写了⼏个巡逻机器⼈，放置在迷宫⾥。由于⼩ G ⻓年待在⿊暗势⼒内部，早已脆弱不堪，⼀旦⼩ G 和机器⼈相遇，他就 GG 了。⽽且，传承⾃ fot 优秀的时空折叠技术，机器⼈会瞬移，⽽不受⻔的影响。你可以理解为它们不会经过任意⼀扇⻔，所以⼩ G 不会在从⼀个房间⾄另⼀个房间的路途中 GG。

这可怎么办呢？由于⼩ G 深谙敌军的组成和习性，知道某⼈总是造锅，导致了⼈⼯智能智障化⸺它们仅仅会周期性的游⾛。⼩ G 已经掌握了源码中的错误，知晓了每个机器⼈的游⾛房间顺序，和周期 $T$。它们会在第 $1$ 时刻出现并开始按照顺序遍历，所以⼩ G 在第 $0$ 时刻不会受到影响，⼩ G 不会开场 GG。

那么问题来了，由于⼩ G 忙于逃跑，他想询问，需要多⼤的⼒⽓才能逃出地牢。当然，由于从第 $0$ 时刻到第 $1$ 时刻只有 $1.001s$，他要⽤ $0.001s$ 的时间锻炼⾝体来获取最低的⼒量值，所以，你只有 $1s$ 的时间来回答这个问题。如果⽆论如何都不能逃出去，请输出 impossible。

请注意：任意时刻⼩ G 必须经过⼀扇⻔，如果某⼀时刻⼩ G ⽆路可⾛，也请输出 impossible。

输入格式

输⼊第⼀⾏，三个个⾮负整数 $n,m,k$，表⽰房间的个数和⻔的数量以及终点恰好开放的时间。

接下来 $m$ ⾏，每⾏有三个数 $u,v,w$，分别表⽰⻔的两边与推开此⻔的最⼩⼒量值。

第 $m+2$ ⾏有⼀个⾮负整数 $num$，表⽰机器⼈的数量，和两个正整数 $S,T$，表⽰起点与终点。

接下来 $num$ ⾏，每⾏第⼀个为 $t_i$，表⽰第 $i$ 个机器⼈的周期，后⾯会有个 $t_i$ 正整数，表⽰机器⼈依次遍历的房间。

输出格式

输出⼀个数，表⽰你最⼩需要的⼒量值。

样例

4 5 3
1 2 3
2 4 6
3 2 4
1 4 5
2 3 4
2 1 3
2 2 1
3 2 1 4

6

第 $0$ 时刻，⼩ G 在 $1$ 房间，机器⼈尚未出现。

在第 $1$ 时刻，⼩ G 从 $1$ 房间到 $4$ 房间，需要⼒量值 $5$，机器⼈ $1,2$出现在 $2$ 房间。

在第 $2$ 时刻，⼩ G 从 $4$ 房间到 $2$ 房间，需要⼒量值 $6$，此时机器⼈ $1,2$ 从 $2$ 房间到 $1$ 房间。

在第 $3$ 时刻，⼩ G 从 $2$ 房间到 $3$房间，需要⼒量值 $4$，此时机器⼈ $1$ 从 $1$ 房间到 $2$ 房间，机器⼈ $2$ 从 $2$ 房间到 $4$ 房间。

综上，⼩ G 需要最⼩的⼒量值 $6$。可以证明上述过程合法且不存在更优解。

3 3 2
1 2 3
2 3 2
1 3 1
2 1 3
2 1 2
2 2 3

impossible

数据范围

对于前 $10\%$ 的数据，$m=0$。

对于另外 $20\%$ 的数据，对于任意 $i$，都有 $t_i=1$。

对于另外 $20\%$ 的数据，推开所有⻔的⼒量值⼀样。

对于前 $60\%$ 的数据，$n\le 15$，$m\le 100$，$k\le 10^4$。

对于全部数据，$0\le n\le 50$，$0\le m\le 1600$，$0\le k\le 10^8$，$0\le num\le 10$，$1\le t_i\le 4$，$0\le w\le 10^6$。