回家的路

Bajtogród 的路网由n 个路口和 m 条双向道路组成。每条道路连接两个不同的路口，且任意两个路口之间最多只有一条直接道路。道路可能经过隧道或高架桥。

路口 1 附近有一所学校，Bajtek 每天在那里上学，而路口 n 附近是他的家。早上，父母会开车送他去学校，但放学后他需要自己乘坐公共交通回家。今年公交车的时刻表又一次调整了。由于 Bajtogród 只提供单程票，每次上车都需要检票，Bajtek 决定制定一个最快的回家计划，且换乘次数不超过 k 次。请你帮帮他！

每条公交线路的车辆都会按照固定的路线行驶，经过某些路口，并在每个路口停靠，供乘客上下车。同一线路的公交车会按照固定的时间间隔发车（具体细节见输入格式）。我们假设以下时间可以忽略不计：

公交车在路口的停靠时间；

从一辆公交车换乘到另一辆公交车的时间（假设无需等待）；

从学校走到路口 1 以及从路口 n 走回家的时间。

输入的第一行包含五个整数 n, m, s, k, t (2 \leq n \leq 10000, 1 \leq m \leq 50000, 1 \leq s \leq 25000, 0 \leq k \leq 100, 0 \leq t \leq 10^{9})，分别表示路口数量、道路数量、公交线路数量、Bajtek 最多允许的换乘次数，以及他离开学校的分钟数。路口编号从 1 到 n。

接下来的 m 行描述道路，每行包含三个整数 a, b, c (1 \leq a, b \leq n, a \neq b, 1 \leq c \leq 10^{9})，表示编号为 a 和 b 的路口之间有一条双向道路，乘坐任何经过这条路的公交车通过它需要 c 分钟。每对无序路口对 {a, b} 在输入中最多出现一次。

接下来的 2s 行描述公交线路，每条线路的描述占用两行。第一行包含三个整数 \ell, x, y (2 \leq \ell \leq n, 0 \leq x \leq 10^9, 1 \leq y \leq 10^9)，第二行包含 \ell个两两不同的整数 v_1, v_2, ... , v\ell (1 \leq v_i \leq n)。这表示该线路的公交车从路口 v_1 在 x + j · y (j = 0, 1, 2, ...) 分钟发车，然后依次经过路口 v_2, v_3, ... , v\ell。保证对于 1 \leq i < l，路口 v_i 和 vi+1 之间存在一条道路。

所有公交线路的 \ell 之和不超过 50000。

你的程序应输出一行，包含一个整数，表示 Bajtek 从学校离开后能到达家的最早分钟数。如果 Bajtek 无法在 t 分钟后回家，则应输出 NIE。

POI