Move It, Slowpoke!

문제

Centerville has a bit of a problem. Because of recent road construction many slow-moving vehicles (garbage trucks, delivery trucks, etc) have been rerouted through town. Many of the citizens (or at least this problem contributor) are becoming increasingly upset about being stuck behind these vehicles, especially when they stay on one continuous road for an extended period of time. The town council has recently enacted an ordinance stating that no slow-moving vehicle can stay on any two or more roads considered "continuous" past a distance $dd$. The details of the ordinance are the following:

1. The ordinance begins with a definition of what a "slow-moving vehicle" is. That's not important for us here (though you know one when you see one).
2. The ordinance next lists the ordered pairs of roads in town that are considered "continuous". Slow-moving vehicles are allowed to drive on either road in a pair separately (even if the length of either road is $>d>\; d$), but cannot drive on the first road followed immediately by the second road if the total length of the pair is $>d>\; d$. Note that if the second road of one continuous pair matches the first road of another continuous pair, then the three roads in the two pairs are together considered continuous. In other words, if (say) A $\to \backslash rightarrow$ B $\to \backslash rightarrow$ C is considered continuous and B $\to \backslash rightarrow$ C $\to \backslash rightarrow$ D is considered continuous, then A $\to \backslash rightarrow$ B $\to \backslash rightarrow$ C $\to \backslash rightarrow$ D is considered continuous.
3. The ordinance ends with methods to determine $dd$ (again, these details are not important to us here).

Obviously the owners of these slow-moving vehicles are a bit perturbed (serves them right I say, but again that's not important to us). While finding the shortest path between two points used to be straight-forward (no pun intended), now it's become a bit of a challenge given the restrictions placed on them---in fact, it may not even be possible to get from one point to another. For example, consider the set of roads in Figure 1. Assume that a slow-moving truck must get from intersection A to intersection D, and that three pairs of roads are considered continuous: A $\to \backslash rightarrow$ B $\to \backslash rightarrow$ C; A $\to \backslash rightarrow$ B $\to \backslash rightarrow$ E; and B $\to \backslash rightarrow$ F $\to \backslash rightarrow$ G. If $dd$ is $3030$ (or higher), then the truck can drive A $\to \backslash rightarrow$ B $\to \backslash rightarrow$ C $\to \backslash rightarrow$ D. If $dd$ is $2525$, this route is no longer usable, so the shortest path is now A $\to \backslash rightarrow$ B $\to \backslash rightarrow$ E $\to \backslash rightarrow$ C $\to \backslash rightarrow$ D (Sample Input 1). If $dd$ is $1515$, then A $\to \backslash rightarrow$ B $\to \backslash rightarrow$ E is not longer usable, so the shortest route is now A $\to \backslash rightarrow$ B $\to \backslash rightarrow$ F $\to \backslash rightarrow$ G $\to \backslash rightarrow$ C $\to \backslash rightarrow$ D (note that in this case you are allowed to drive from A to B even though the length of that road is $>d>\; d$). Finally, if $dd$ is , then it is impossible for this truck to drive from A to D (Sample Input 2). Note that slow-moving vehicles are unable to perform u-turns without causing even more delays, so, for example, the path A $\to \backslash rightarrow$ B $\to \backslash rightarrow$ F $\to \backslash rightarrow$ B $\to \backslash rightarrow$ C $\to \backslash rightarrow$ D is not possible for any value of $dd$.

Figure 1: Example road network, used by Sample Inputs 1 and 2.

Given a specification of the road network, two intersections $ss$ and $tt$, and a value for $dd$, the owners of the slow-moving vehicles would like to know the shortest distance to travel from intersection $ss$ to intersection $tt$.

입력

Input starts with a line containing 6 integers $nn$ $mm$ $kk$ $dd$ $ss$ $tt$, where $nn$ ($2\le n\le 1002\; \backslash leq\; n\; \backslash leq\; 100$) is the number of intersections in the town (numbered 1 to $nn$), $mm$ is the number of roads between intersections, $kk$ ($0\le k\le m(m-1)0\; \backslash leq\; k\; \backslash leq\; m(m-1)$) is the number of ordered pairs of roads that are considered as continuous when driven consecutively, $dd$ ($1\le d\le 1001\; \backslash leq\; d\; \backslash leq\; 100$) is the longest distance that slow-moving vehicles can stay on a continuous sequence of roads, $ss$ ($1\le s\le n1\; \backslash leq\; s\backslash leq\; n$) is the intersection to travel from, and $tt$ ($1\le t\le n,s\mathrm{\ne }t1\backslash leq\; t\; \backslash leq\; n,\; s\backslash neq\; t$) is the intersection to travel to. Following this are $mm$ lines, consisting of three integers $aa$, $bb$, $\mathrm{\ell }\backslash ell$ ($1\le a,b\le n1\; \backslash leq\; a,b\; \backslash leq\; n$, $a\mathrm{\ne }ba\; \backslash neq\; b$, $1\le \mathrm{\ell }\le 1001\backslash leq\; \backslash ell\; \backslash leq\; 100$) indicating a two-way road of length $\mathrm{\ell }\backslash ell$ connects intersections $aa$ and $bb$. There is at most one road between any two intersections. Following this are $kk$ lines, of the form $aa$ $bb$ $cc$ ($a\mathrm{\ne }b,a\mathrm{\ne }c,b\mathrm{\ne }ca\; \backslash neq\; b,\; a\backslash neq\; c,\; b\backslash neq\; c$) indicating that driving on the road from $aa$ to $bb$ followed by the road from $bb$ to $cc$ is considered as continuous driving. It is guaranteed that there is a road between $aa$ and $bb$ and that there is a road between $bb$ and $cc$. Note that this does not mean that the reverse order of driving on those roads is considered continuous driving.

출력

If it is impossible to travel from $ss$ to $tt$ output impossible; otherwise output the shortest distance to travel from $ss$ to $tt$.

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