题目描述

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<14$，卡车无法从 $\texttt{A}$ 前往 $\texttt{D}$，对应样例二。

慢速车辆无法在不造成更多延误的情况下掉头。因此，例如路径 $\texttt{A}\to\texttt{B}\to\texttt{F}\to\texttt{B}\to\texttt{C}\to\texttt{D}$ 对任何 $d$ 都不可行。

给定道路网络、起点路口 $s$、终点路口 $t$ 和限制值 $d$，求慢速车辆从 $s$ 前往 $t$ 的最短行驶距离。

:::align{center} :::

输入格式

第一行包含六个整数 $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$ 的最短行驶距离。

7 8 3 25 1 7
1 2 20
2 3 10
2 4 4
4 3 8
2 5 6
5 6 8
6 3 4
3 7 10
1 2 3
1 2 4
2 5 6

42

7 8 3 12 1 7
1 2 20
2 3 10
2 4 4
4 3 8
2 5 6
5 6 8
6 3 4
3 7 10
1 2 3
1 2 4
2 5 6

impossible