Problem Description

There are $n$ points and $m$ edges, with no duplicate edges or self-loops, and each edge has a length.

Point $1$ is the school, and point $n$ is home.

There are $s$ bus routes. Buses stop at every point and a point will not be stopped at twice. The travel time on an edge is equal to its length. The first bus departure time and the interval between buses are given.

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

Only travel and waiting times are considered. Transfer times are not counted.

Input Format

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

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

The next $2s$ lines describe the bus routes in pairs:

• The first line of each pair contains three integers $l, x, y$, indicating it stops at $l$ points, the first bus departs at time $x$, and the interval between buses is $y$.
• The second line of each pair contains $l$ integers $v_1, \dots, v_l$, listing the $l$ points it stops at in order.

Output Format

Output a single integer, the answer.

If it is not possible to reach home, output a single string NIE.

Sample Input and Output

Sample Input #1

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

Sample Output #1

8

Sample Input #2

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

Sample Output #2

132

Notes/Hints

For all data, $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$.

见题面 Input 部分

见题面 Output 部分