题目描述

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}, \ldots, v_{\ell}$ $(1 \leq v_{i} \leq n)$。这表示该线路的公交车从路口 $v_{1}$ 在 $x + j \cdot y$ $(j = 0, 1, 2, \ldots)$ 分钟发车，然后依次经过路口 $v_{2}, v_{3}, \ldots, v_{\ell}$。保证对于 $1 \leq i < l$，路口 $v_i$ 和 $v_{i+1}$ 之间存在一条道路。

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

输出格式

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

4 4 2 1 1
1 2 2
2 3 4
1 3 3
4 3 2
4 0 10
1 2 3 4
3 2 7
1 3 2

8

样例 2

见附加文件下 [dro1.in](file:dro1.in) 和 [dro1.out](file:dro1.out)。

该样例满足 $n=10, m=45, k=10, t=123$，编号相邻的路口之间有长度为 $1$ 的道路，其他路口对之间有长度为 $100$ 的道路；公交车从 $0$ 分钟开始运行，每分钟都有车在相邻或相隔 $1$ 的路口之间运行，答案是 $132$；

样例 3

见附加文件下 [dro2.in](file:dro2.in) 和 [dro2.out](file:dro2.out)。

该样例满足 $n=103, m=102, k=100, t=0$，编号相邻的路口之间有长度为 $1$ 的道路，其他路口对之间没有直接道路；有一辆公交车在 $10^{9}$ 分钟发车，经过路口 $(1, 2, 3, \ldots, n)$，还有一些公交车从 $0$ 分钟开始运行，覆盖所有相邻路口对，答案是 $10^{9}+102$；

样例 4

见附加文件下 [dro3.in](file:dro3.in) 和 [dro3.out](file:dro3.out)。

该样例满足 $n=10000, m=17891, s=7891, k=50, t=0$，答案是 $11100000071$。

数据范围与提示

详细子任务附加限制及分值如下表所示。