### 问题描述 在一个大型购物中心内，有多个商店。顾客经常需要从一个商店去到另一个商店。中心内的通道很复杂，有些通道因为装修或其他原因可能暂时关闭。管理者想要为顾客提供一个服务，通过输入起点和终点商店，可以为顾客提供前 $k$ 条最短的通行路径。 但是，由于购物中心内有一些特定的商店正在进行促销活动，管理者希望这 $k$ 条路径中的每条路径都能经过至少一个正在促销的商店。 请你设计一个程序，帮助购物中心实现这个功能。 ### 输入格式 第一行包含三个整数 $n$，$m$ 和 $k$。其中 $n$ 代表商店的数量，$m$ 代表通道的数量，$k$ 代表需要的路径数量。 接下来的 $m$ 行，每行包含三个整数 $a$，$b$ 和 $w$。表示商店 $a$ 和商店 $b$ 之间有一个通道，长度为 $w$。 接下来的一行包含一个整数 $p$，表示正在促销的商店数量。 接下来的一行包含 $p$ 个整数，表示正在促销的商店编号，商店编号从 $1$ 开始。 最后一行包含两个整数 $s$ 和 $t$，表示起点商店和终点商店。 ### 输出格式 输出 $k$ 行，每行输出该路径的长度。如果不足 $k$ 条符合条件的路径，那么只输出存在的路径，若没有任何一条路径符合条件则输出 `None`。 ### 样例输入 ``` 5 6 2 1 2 1 1 3 2 2 3 1 3 4 2 3 5 1 4 5 3 2 2 3 1 5 ``` ### 样例输出 ``` 3 3 ``` ### 样例说明 从商店 $1$ 到商店 $5$ 有很多路径，但最短的前两条路径是： 1. $1 \rightarrow 2 \rightarrow 3 \rightarrow 5$，长度为 $3$。 2. $1 \rightarrow 3 \rightarrow 5$，长度为 $3$。 这两条路径都经过了正在促销的商店。 ### 测评数据规模 $2 \leq n \leq 100$，$1 \leq m \leq 5000$，$1 \leq k \leq 10$，$w$ 的范围为 $[1, 1000]$，$p$ 的范围为 $[1, n]$，$s \neq t$。