Problem D
Natural Navigation

This majestic footpath has the colours red, white, purple and green. SOURCE: Botanical Garden München-Nymphenburg.

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?

Input

The input consists of:

• A line containing the number of intersections $n$ ($1 \leq n \leq 5 \cdot 10^5$), the number of footpaths $m$ ($1 \leq m \leq 5 \cdot 10^5$) and the number of distinct colours $k$ ($1 \leq k \leq 1\, 000$).

• $m$ pairs of lines describing the directed footpaths, each formatted as follows:

  • One line with three integers $u$, $v$ and $t$ ($1 \le u,v \le n, 1 \le t \le 10^6$), meaning that the footpath leads from intersection $u$ to intersection $v$ and it takes $t$ seconds to walk along this footpath.

  • One line with an integer $\ell $ ($1 \leq \ell \leq k$), followed by $\ell $ distinct integers $c_1,\dots ,c_\ell $ ($1 \le c_i \le k$ for each $i$), listing the colours that appear along this footpath.

The sum of $\ell $ over all footpaths does not exceed $5 \cdot 10^5$. Note that, as you would imagine in a botanic garden, a footpath can lead back to the intersection it started from and multiple footpaths can exist between a pair of intersections. Moreover, it is not guaranteed that each intersection can be reached via the footpaths.

Output

If it is impossible to lead the user to intersection $n$, output impossible. Otherwise output a single integer, the time it will take to reach the target in seconds. We are only considering the time spent walking along the footpaths.

4 6 2
1 2 6
1 1
1 3 3
1 2
2 3 5
1 2
2 4 8
1 1
3 1 4
2 1 2
3 4 3
1 1

14

3 4 3
1 2 300
2 1 2
2 1 2000
2 3 1
1 3 80
2 2 1
2 2 42
1 2

impossible