Migrated from Lutece 2712 顶点游走

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

你现在正在进行一个顶点游走游戏

给你一张 $n$ 个点 $m$ 条边的有向图，你现在从 $1$ 号点出发， 需要多久时间才能到达终点 $n$ 号点？

显然这个游戏对你来说太简单了，因此现在要给你加上一系列限制来让你能玩更久。

现在我们给这 $m$ 条边赋上权值 $c_i$ ，表示你只有在走过的边的总次数达到 $d_{c_i}$ 时才能走这条边，注意一条边可以被多次计算。

现在你想知道是否可以到达终点，如果可以的话，他想知道至少需要多少步才能到达。

Input

第一行三个整数 $n, m, c$ .

接下来 $m$ 行，每行三个整数 $u, v, lv$ ，表示有一条 $u$ 到 $v$ 的线路，等级为 $lv$ .

接下来一行 $c$ 个整数，第 $i$ 个表示 $d_i$ .

Output

若不能到达输出 Impossible。

否则输出一个整数表示他至少要经过的边数

Samples

3 3 2
1 2 1
2 1 1
2 3 2
0 2

4

3 2 2
1 2 1
2 3 2
0 2

Impossible

Constraints

$2 \leq n \leq 180, 1 \leq c \leq 50, 0 \leq m \leq 4 × 10^4, 0 \leq d_i \leq d_{i+1} \leq 10^9$.

可能有重边或者自环

Resources

2022 UESTC ICPC Training for Graph