{"raw_statement":[{"iden":"background","content":"译自 [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/)。\n\nd1t1。"},{"iden":"statement","content":"$n$ 个点，$m$ 条边，无重边自环，边有长度。\n\n$1$ 号点是学校，$n$ 号点是家。\n\n$s$ 条公交线路。公交逢点必停，且一个点不会停两次。在一条边上行驶的时间就是它的长度。给定了第一班公交发车时间和发车间隔。\n\n在时刻 $t$ 从学校出发，至多换乘 $k$ 次，求最早什么时候到家。\n\n只计算路上时间和等车时间。换乘时间不计。"},{"iden":"input","content":"第一行：五个整数 $n,m,s,k,t$。\n\n接下来 $m$ 行：每行三个整数 $a,b,c$，表示有一条边连接 $a,b$，长度为 $c$。\n\n接下来 $2s$ 行：每两行描述一条公交线路：\n\n- 第一行三个整数 $l,x,y$，表示它共停靠 $l$ 个点，第一班在时刻 $x$ 发车，每两班之间时间间隔为 $y$。\n- 第二行 $l$ 个整数 $v_1,\\dots,v_l$，依次为它停靠的 $l$ 个点。"},{"iden":"output","content":"一行一个整数，答案。\n\n如果不能到家，那么输出一行一个字符串 `NIE`。"},{"iden":"note","content":"样例解释：![](https://cdn.luogu.com.cn/upload/image_hosting/9njsvc34.png)\n\n对于全部数据，$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$。\n\n| 子任务编号 | 限制 | 分数 |\n| :----------: | :----------: | :----------: |\n| 1 | $k=n$ | 20 |\n| 2 | $v_i<v_{i+1}$ | 20 |\n| 3 | $l=2$ | 20 |\n| 4 | $t=0,x=0,y=1$ | 20 |\n| 5 |  | 20 |\n"}],"translated_statement":null,"sample_group":[["4 4 2 1 1\n1 2 2\n2 3 4\n1 3 3\n4 3 2\n4 0 10\n1 2 3 4\n3 2 7\n1 3 2\n","8"],["10 45 17 10 123\n1 2 1\n1 3 100\n1 4 100\n1 5 100\n1 6 100\n1 7 100\n1 8 100\n1 9 100\n1 10 100\n2 3 1\n2 4 100\n2 5 100\n2 6 100\n2 7 100\n2 8 100\n2 9 100\n2 10 100\n3 4 1\n3 5 100\n3 6 100\n3 7 100\n3 8 100\n3 9 100\n3 10 100\n4 5 1\n4 6 100\n4 7 100\n4 8 100\n4 9 100\n4 10 100\n5 6 1\n5 7 100\n5 8 100\n5 9 100\n5 10 100\n6 7 1\n6 8 100\n6 9 100\n6 10 100\n7 8 1\n7 9 100\n7 10 100\n8 9 1\n8 10 100\n9 10 1\n2 0 1\n1 2\n2 0 1\n1 3\n2 0 1\n2 3\n2 0 1\n2 4\n2 0 1\n3 4\n2 0 1\n3 5\n2 0 1\n4 5\n2 0 1\n4 6\n2 0 1\n5 6\n2 0 1\n5 7\n2 0 1\n6 7\n2 0 1\n6 8\n2 0 1\n7 8\n2 0 1\n7 9\n2 0 1\n8 9\n2 0 1\n8 10\n2 0 1\n9 10\n","132"],["见附件","1000000102"],["见附件","11100000071"]],"show_order":[],"formal_statement":null,"simple_statement":null,"has_page_source":false}