Natural Navigation

You want to build an app to help people navigate through a large botanic garden. This is difficult, because there are many winding footpaths and intersections offering many choices, making traditional directions such as "turn right" or "move further north" unsuitable. Instead, the app should rely on the garden's greatest resource: the numerous exotic plants and their diverse colours. Whenever a user is at an intersection, the app will know where they are and will display one particular colour accordingly. The user will then follow a footpath where this colour is visible. If the colour can be spotted along multiple footpaths originating from the intersection, the user is free to choose any of these footpaths.

You have been given a perfect model of the botanic garden, consisting of $n$ intersections (numbered from $1$ to $n$) and $m$ footpaths going between those. To keep order, each footpath can only be used in the given direction. Currently, the plants are exhibiting $k$ different colours (numbered from $1$ to $k$) and for each footpath, you are given a list of all the colours that are visible along it when viewed from the intersection where it starts. A user is currently at intersection $1$ and wants to navigate to intersection $n$. You can assume that the user will follow the app's directions perfectly, but whenever faced with multiple options (because the given colour is visible along multiple footpaths), you have to assume they will make the worst possible choice. How long will it take to reach the target when your app gives the best possible instructions?

The first line contains $n$ ($1 \leq n \leq 5 \cdot 10^5$), $m$ ($1 \leq m \leq 5 \cdot 10^5$), and $k$ ($1 \leq k \leq 1\,000$).

Then $m$ footpaths follow, each described by two lines:

• One line with three integers $u$, $v$, and $t$ ($1 \leq u,v \leq n$, $1 \leq t \leq 10^6$). The footpath leads from intersection $u$ to intersection $v$ and takes $t$ seconds to walk.
• One line with an integer $\ell$ ($1 \leq \ell \leq k$), followed by $\ell$ distinct integers $c_1, \dots, c_\ell$ ($1 \leq c_i \leq k$). These are the colours visible along the footpath.

The sum of $\ell$ over all footpaths does not exceed $5 \cdot 10^5$. A footpath can lead back to its starting intersection, and several footpaths can connect the same pair of intersections. Intersection $n$ is not guaranteed to be reachable from intersection $1$.

If the user cannot be led to intersection $n$, print impossible. Otherwise, print a single integer: the time in seconds to reach intersection $n$. Only the time spent walking along the footpaths is counted.