Background

Translated from XXVIII Olimpiada Informatyczna - Stage III Droga do domu。

d1t1。

Problem Description

There are $n$ vertices and $m$ edges, with no multiple edges or self-loops. Each edge has a length.

Vertex $1$ is the school, and vertex $n$ is home.

There are $s$ bus routes. A bus stops at every vertex on its route, and it will not stop at the same vertex twice. The travel time along an edge equals its length. For each route, the departure time of the first bus and the departure interval are given.

Starting from the school at time $t$, with at most $k$ transfers, find the earliest time you can arrive home.

Only travel time and waiting time are counted. Transfer time is not counted.

Input Format

The first line contains five integers $n,m,s,k,t$.

The next $m$ lines each contain three integers $a,b,c$, indicating an edge between $a$ and $b$ with length $c$.

The next $2s$ lines describe the bus routes, with every two lines describing one route:

• The first line contains three integers $l,x,y$, meaning the route stops at $l$ vertices in total, the first bus departs at time $x$, and the time interval between consecutive buses is $y$.
• The second line contains $l$ integers $v_1,\dots,v_l$, the $l$ vertices the route stops at, in order.

Output Format

Output one integer in one line: the answer.

If it is impossible to get home, output one line containing the string 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

10 45 17 10 123
1 2 1
1 3 100
1 4 100
1 5 100
1 6 100
1 7 100
1 8 100
1 9 100
1 10 100
2 3 1
2 4 100
2 5 100
2 6 100
2 7 100
2 8 100
2 9 100
2 10 100
3 4 1
3 5 100
3 6 100
3 7 100
3 8 100
3 9 100
3 10 100
4 5 1
4 6 100
4 7 100
4 8 100
4 9 100
4 10 100
5 6 1
5 7 100
5 8 100
5 9 100
5 10 100
6 7 1
6 8 100
6 9 100
6 10 100
7 8 1
7 9 100
7 10 100
8 9 1
8 10 100
9 10 1
2 0 1
1 2
2 0 1
1 3
2 0 1
2 3
2 0 1
2 4
2 0 1
3 4
2 0 1
3 5
2 0 1
4 5
2 0 1
4 6
2 0 1
5 6
2 0 1
5 7
2 0 1
6 7
2 0 1
6 8
2 0 1
7 8
2 0 1
7 9
2 0 1
8 9
2 0 1
8 10
2 0 1
9 10

132

见附件

1000000102

见附件

11100000071

Hint

Sample explanation:

For all testdata, $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$。

Translated by ChatGPT 5