집으로 가는 길

바이트고르드의 도로망은 교차로 $n$개와 이를 잇는 양방향 도로 $m$개로 이루어져 있다. 각 도로는 서로 다른 두 교차로를 잇는다. 두 교차로를 잇는 도로는 최대 하나뿐이다. 도로는 터널과 고가도로를 지날 수 있다.

교차로 1번에는 바이테크가 다니는 학교가 있고, 교차로 $n$번에는 그의 집이 있다. 아침에는 부모님이 학교까지 태워 주지만, 집에 갈 때는 혼자 시내버스를 탄다. 올해 버스 시간표가 또 바뀌었다. 바이트고르드에서는 승차할 때마다 찍는 일회용 승차권만 쓸 수 있다. 그래서 바이테크는 환승을 최대 $k$번만 하는 가장 빠른 귀갓길을 찾고자 한다. 도와주자!

각 노선의 버스는 정해진 경로를 따라 달리며 일부 교차로를 지난다. 버스는 그 교차로마다 정차하며, 승객은 타거나 내릴 수 있다. 같은 노선의 버스는 일정한 간격으로 출발한다. 자세한 내용은 입력 섹션에 적혀 있다.

정차 시간, 버스 사이의 환승 시간(버스를 기다릴 필요가 없는 경우), 학교에서 교차로 1번까지 걷는 시간, 교차로 $n$번에서 집까지 걷는 시간은 무시할 만큼 작다고 가정한다.

첫 줄에 정수 $n$, $m$, $s$, $k$, $t$가 주어진다($2 \le n \le 10000$, $1 \le m \le 50000$, $1 \le s \le 25000$, $0 \le k \le 100$, $0 \le t \le 10^9$). 차례대로 교차로 수, 도로 수, 버스 노선 수, 최대 환승 횟수, 바이테크가 학교를 나서는 시각(분)이다. 교차로는 1번부터 $n$번까지 번호가 매겨져 있다.

다음 $m$개의 줄에는 $a$, $b$, $c$가 주어진다($1 \le a, b \le n$, $a \ne b$, $1 \le c \le 10^9$). 교차로 $a$와 $b$는 양방향 도로로 연결되어 있고, 이 도로를 지나는 버스는 $c$분이 걸린다. 순서를 무시한 같은 쌍은 한 번만 나온다.

$s$개의 버스 노선은 각각 두 줄로 주어진다. 첫 줄에는 $\ell$, $x$, $y$가 있다($2 \le \ell \le n$, $0 \le x \le 10^9$, $1 \le y \le 10^9$). 둘째 줄에는 서로 다른 정수 $v_1, \ldots, v_\ell$이 있다($1 \le v_i \le n$). 이 노선의 버스는 $j = 0, 1, 2, \ldots$에 대해 $x + j \cdot y$분에 교차로 $v_1$에서 출발하고, 이후 $v_2, v_3, \ldots, v_\ell$ 순서로 지난다. 모든 노선의 $\ell$ 합은 50000을 넘지 않는다.

바이테크가 $t$분에 학교를 나섰을 때 집에 도착할 수 있는 가장 이른 시각(분)을 정수 하나로 출력한다. 집에 도착할 방법이 없으면 대신 NIE라는 단어 하나를 출력한다.

설명: 위 그림은 예제 테스트의 바이트고르드 도로망이다. 원은 번호가 적힌 교차로이고, 선은 이동 시간이 적힌 도로이다. 버스 노선 1의 경로는 빨간색, 노선 2의 경로는 파란색으로 표시되어 있다.

바이테크는 $t = 1$분에 학교를 나서고, 2분에 도착하는 노선 2 버스를 기다린다. 그 버스를 타고 교차로 3번까지 간 뒤, 6분에 노선 1 버스로 갈아탄다. 이 버스는 8분에 그를 집 앞까지 데려다준다.

$k = 0$이라면 바이테크는 교차로 1번에서 노선 1 버스를 기다려야 한다. 이 버스는 10분에 출발해 18분에 그를 집까지 데려다준다.