자연스러운 길 안내

아주 큰 식물원에서 사람들이 길을 찾도록 돕는 앱을 만들려고 합니다. 식물원에는 구불구불한 산책로와 여러 선택지를 주는 교차로가 많아서 "오른쪽으로 도세요"나 "북쪽으로 더 가세요" 같은 기존 안내는 적합하지 않습니다. 대신 앱은 식물원의 가장 큰 자원인 다양한 외래 식물과 그 색을 활용합니다. 사용자가 교차로에 도착하면 앱은 사용자의 위치를 알고 있고, 그 위치에 맞는 특정 색 하나를 표시합니다. 사용자는 그 색이 보이는 산책로를 따라갑니다. 같은 색이 교차로에서 출발하는 여러 산책로에서 보이면 사용자는 그중 어느 산책로든 고를 수 있습니다.

식물원의 완벽한 모델이 주어집니다. 모델은 $n$개의 교차로(1부터 $n$까지 번호)와 이들을 잇는 $m$개의 산책로로 이루어집니다. 질서를 위해 각 산책로는 주어진 방향으로만 이용할 수 있습니다. 현재 식물들은 $k$가지 색(1부터 $k$까지 번호)을 보이고 있으며, 각 산책로마다 그 산책로가 시작되는 교차로에서 바라볼 때 보이는 모든 색의 목록이 주어집니다. 사용자는 지금 교차로 1에 있고 교차로 $n$으로 가려고 합니다. 사용자는 앱의 안내를 완벽하게 따른다고 가정합니다. 다만 주어진 색이 여러 산책로에서 보여 선택지가 생기면, 사용자가 가장 나쁜 선택을 한다고 가정해야 합니다. 앱이 가장 좋은 안내를 줄 때 목적지에 도달하는 데 걸리는 시간은 얼마입니까?

첫 줄에 $n$ ($1 \leq n \leq 5 \cdot 10^5$), $m$ ($1 \leq m \leq 5 \cdot 10^5$), $k$ ($1 \leq k \leq 1\,000$)가 주어집니다.

이어서 $m$개의 산책로가 각각 두 줄로 주어집니다.

• 정수 $u$, $v$, $t$ ($1 \leq u,v \leq n$, $1 \leq t \leq 10^6$)가 한 줄에 주어집니다. 산책로는 교차로 $u$에서 $v$로 이어지며, 걷는 데 $t$초가 걸립니다.
• 정수 $\ell$ ($1 \leq \ell \leq k$)과 서로 다른 정수 $\ell$개 $c_1, \dots, c_\ell$ ($1 \leq c_i \leq k$)이 한 줄에 주어집니다. 이는 그 산책로에서 보이는 색의 목록입니다.

모든 산책로의 $\ell$ 합은 $5 \cdot 10^5$을 넘지 않습니다. 산책로는 출발한 교차로로 되돌아올 수 있고, 같은 두 교차로를 잇는 산책로가 여러 개 있을 수도 있습니다. 교차로 1에서 교차로 $n$에 도달할 수 있다는 보장은 없습니다.

사용자를 교차로 $n$으로 안내할 수 없으면 impossible을 출력합니다. 그렇지 않으면 교차로 $n$에 도착하기까지 걸리는 시간을 정수 하나로 출력합니다. 산책로를 걷는 데 쓴 시간만 셉니다.