P9402 [POI 2020/2021 R3] Droga do domu
题目背景
译自 [XXVIII Olimpiada Informatyczna - III etap](https://sio2.mimuw.edu.pl/c/oi28-3/dashboard/) [Droga do domu](https://szkopul.edu.pl/problemset/problem/ZfS_tobZ_7xdR6D5s6Tegur3/statement/)。
d1t1。
题目描述
$n$ 个点，$m$ 条边，无重边自环，边有长度。
$1$ 号点是学校，$n$ 号点是家。
$s$ 条公交线路。公交逢点必停，且一个点不会停两次。在一条边上行驶的时间就是它的长度。给定了第一班公交发车时间和发车间隔。
在时刻 $t$ 从学校出发，至多换乘 $k$ 次，求最早什么时候到家。
只计算路上时间和等车时间。换乘时间不计。
输入格式
第一行：五个整数 $n,m,s,k,t$。
接下来 $m$ 行：每行三个整数 $a,b,c$，表示有一条边连接 $a,b$，长度为 $c$。
接下来 $2s$ 行：每两行描述一条公交线路：
- 第一行三个整数 $l,x,y$，表示它共停靠 $l$ 个点，第一班在时刻 $x$ 发车，每两班之间时间间隔为 $y$。
- 第二行 $l$ 个整数 $v_1,\dots,v_l$，依次为它停靠的 $l$ 个点。
输出格式
一行一个整数，答案。
如果不能到家，那么输出一行一个字符串 `NIE`。
说明/提示
样例解释：
对于全部数据，$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$，$1\leq c\leq 10^9$，$2\leq l\leq n$，$0\leq x\leq 10^9$，$1\leq y\leq 10^9$，$1\leq a,b,v\leq n$，$\sum l\leq 50000$。
| 子任务编号 | 限制 | 分数 |
| :----------: | :----------: | :----------: |
| 1 | $k=n$ | 20 |
| 2 | $v_i