P17349 [ECNA 2025] Move it, Slowpoke!

Centerville 遇到了一点麻烦。由于近期道路施工，许多行驶缓慢的车辆（垃圾车、送货车等）被改道引入城区。许多市民——至少包括本题作者——越来越受不了被困在这些车辆后面，尤其是它们长时间沿着一条连续道路行驶时。 市议会最近颁布条例：慢速车辆在任何由两条或更多“连续”道路组成的路段上，连续行驶距离不得超过 $d$。条例的细节如下： 1. 条例首先定义了什么是“慢速车辆”。这对本题并不重要——不过看到它时你自然会认出来。 2. 条例列出了城中哪些有序道路对在依次行驶时被视为“连续”。慢速车辆可以单独驶过一对道路中的任意一条，即使其中某一条长度大于 $d$；但如果两条道路的总长度大于 $d$，就不能先驶过第一条再紧接着驶过第二条。 如果一个连续道路对的第二条道路，与另一个连续道路对的第一条道路相同，那么两个道路对涉及的三条道路合在一起也被视为连续。换言之，如果 $\texttt{A}\to\texttt{B}\to\texttt{C}$ 被视为连续，且 $\texttt{B}\to\texttt{C}\to\texttt{D}$ 被视为连续，那么 $\texttt{A}\to\texttt{B}\to\texttt{C}\to\texttt{D}$ 整段都被视为连续。 3. 条例最后规定了如何确定 $d$。这些细节同样与本题无关。 慢速车辆的车主对此当然有些不满。过去，在两点之间寻找最短路径十分直接；如今受这些限制影响，问题变得更有挑战，甚至可能根本无法从一点到达另一点。 例如，考虑图 1 的道路网络。一辆慢速卡车要从路口 $\texttt{A}$ 前往路口 $\texttt{D}$，有三对道路被视为连续：$\texttt{A}\to\texttt{B}\to\texttt{C}$、$\texttt{A}\to\texttt{B}\to\texttt{E}$ 和 $\texttt{B}\to\texttt{F}\to\texttt{G}$。 - 若 $d=30$ 或更大，卡车可以沿 $\texttt{A}\to\texttt{B}\to\texttt{C}\to\texttt{D}$ 行驶； - 若 $d=25$，这条路线不再可用，最短路线变为 $\texttt{A}\to\texttt{B}\to\texttt{E}\to\texttt{C}\to\texttt{D}$，对应样例一； - 若 $d=15$，$\texttt{A}\to\texttt{B}\to\texttt{E}$ 也不再可用，最短路线变为 $\texttt{A}\to\texttt{B}\to\texttt{F}\to\texttt{G}\to\texttt{C}\to\texttt{D}$。注意，此时仍允许从 $\texttt{A}$ 驶到 $\texttt{B}$，尽管这条单独道路的长度大于 $d$； - 若 $d

第一行包含六个整数 $n,m,k,d,s,t$。其中： - $2\le n\le 100$，表示路口数量，编号为 $1$ 到 $n$； - $m$ 表示路口之间的道路数量； - $0\le k\le m(m-1)$，表示依次驶过时被视为连续的有序道路对数量； - $1\le d\le 100$，表示慢速车辆在一段连续道路序列上可以行驶的最大距离； - $1\le s\le n$，表示起点； - $1\le t\le n$ 且 $s\ne t$，表示终点。 接下来的 $m$ 行中，每行包含三个整数 $a,b,\ell$（$1\le a,b\le n$，$a\ne b$，$1\le\ell\le 100$），表示路口 $a,b$ 之间有一条长度为 $\ell$ 的双向道路。任意两个路口之间至多有一条道路。 随后 $k$ 行中，每行包含 $a,b,c$，三者互不相同，表示先沿道路从 $a$ 到 $b$，再沿道路从 $b$ 到 $c$，会被视为连续行驶。保证 $a,b$ 之间以及 $b,c$ 之间都有道路。注意，这不意味着反向依次驶过这两条道路也被视为连续。

如果无法从 $s$ 到达 $t$，输出 `impossible`；否则输出从 $s$ 到 $t$ 的最短行驶距离。