森特维尔市（Centerville）遇到了一个问题。由于最近的道路施工，许多慢速车辆（如垃圾车、送货卡车等）被改道途经镇上。许多市民（或者至少是本题的命题人）对于被堵在这些车辆后面感到越来越沮丧，特别是当这些车辆在一条连续的道路上行驶很长时间时。镇议会最近颁布了一项法令，规定任何慢速车辆在被视为“连续”的两条或更多条道路上行驶的连续距离不能超过 $d$。该法令的具体细节如下：

1. 法令首先定义了什么是“慢速车辆”。这在这里对我们并不重要（尽管你一看到就会知道）。
2. 法令接着列出了镇上被视为“连续”的道路有序对。慢速车辆允许单独在有序对中的任意一条道路上行驶（即使其中某条道路的长度 $> d$），但如果该有序对的两条道路总长度 $> d$，则不能在行驶完第一条道路后立即行驶第二条道路。请注意，如果一个连续道路对的第二条道路与另一个连续道路对的第一条道路相同，则这两个对中的三条道路一起被视为连续的。换句话说，如果（例如）$A \to B \to C$ 被视为连续，且 $B \to C \to D$ 被视为连续，那么 $A \to B \to C \to D$ 也被视为连续。
3. 法令最后给出了确定 $d$ 的方法（同样，这些细节对我们并不重要）。

显然，这些慢速车辆的车主感到有些不安（我说他们活该，但同样，这对我们并不重要）。虽然以前寻找两点之间的最短路径非常简单直接，但鉴于对它们施加的限制，现在这已经变成了一个挑战——事实上，甚至可能无法从一个点到达另一个点。例如，考虑图 1 中的道路集。假设一辆慢速卡车必须从路口 A 前往路口 D，并且有三对道路被视为连续：$A \to B \to C$、$A \to B \to E$ 以及 $B \to F \to G$。如果 $d$ 为 30（或更高），则卡车可以行驶 $A \to B \to C \to D$。如果 $d$ 为 25，此路线将不再可用，因此最短路径变为 $A \to B \to E \to C \to D$（样例输入 1）。如果 $d$ 为 15，则 $A \to B \to E$ 不再可用，因此最短路线变为 $A \to B \to F \to G \to C \to D$（请注意，在这种情况下，即使道路 $A \to B$ 的长度 $> d$，你仍然被允许从 A 行驶到 B）。最后，如果 $d < 14$，则该卡车不可能从 A 行驶到 D（样例输入 2）。请注意，慢速车辆无法在不造成更多延迟的情况下进行掉头，因此，例如，对于任何 $d$ 值，路径 $A \to B \to F \to B \to C \to D$ 都是不可能的。

图 1：样例输入 1 和 2 中使用的示例道路网络。

给定道路网络的说明、两个路口 $s$ 和 $t$ 以及 $d$ 的值，慢速车辆的车主希望知道从路口 $s$ 到路口 $t$ 的最短行驶距离。

输入格式

输入的第一行包含 6 个整数 $n, m, k, d, s, t$，其中：

• $n$（$2 \le n \le 100$）是镇上的路口数量（编号为 $1$ 到 $n$）；
• $m$ 是路口之间的道路数量；
• $k$（$0 \le k \le m(m-1)$）是连续行驶时被视为连续的道路有序对的数量；
• $d$（$1 \le d \le 100$）是慢速车辆在连续道路序列上可以行驶的最长距离；
• $s$（$1 \le s \le n$）是出发路口；
• $t$（$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$），表示一条长度为 $\ell$ 的双向道路连接路口 $a$ 和 $b$。任意两个路口之间最多只有一条道路。

接下来有 $k$ 行，格式为 $a\ b\ c$（$a \ne b, a \ne c, b \ne c$），表示先在从 $a$ 到 $b$ 的道路上行驶，紧接着在从 $b$ 到 $c$ 的道路上行驶，被视为连续行驶。保证 $a$ 和 $b$ 之间存在道路，且 $b$ 和 $c$ 之间存在道路。请注意，这并不意味着以相反的顺序（即从 $c$ 到 $b$ 再到 $a$）行驶也被视为连续行驶。

输出格式

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

样例

样例输入 1

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

样例输出 1

42

样例输入 2

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

样例输出 2

impossible