Walking around the campus has become a part of our life. We attend class in CS building, have a meal in restaurant, and go back to sleep in your dorm.
Peter thinks that it takes too much time to move between two places. He always wants to reach a place as fast as possible. So he often cuts the corner between two places by passing lawn. However, it is harmful to walk on lawn. Since he doesn’t want to do more harm on lawn, Peter makes a trade-off. He hopes to reach destination without using more than a certain time, so he might not need to pass every short-cut. As a friend of Peter, you want to compute the minimum number of short-cut he has to take to encourage him.
There are no more than 50 test cases. The first line of each test case contains an integer n, indicating the number of places. (1 ≤ n ≤ 100) The parts are numbered from 1 to n. The second line contains an integer M, indicating the number of roads. Then M lines in the form "a b c", which mean there is a road between the ath place and the bth place and takes c minutes to walk along it. Then an integer S and S lines follow, describing the short-cuts with the same way as the roads. The next contains two integers indicating the places to which the start and the destination. The last line contains one integer T, the time limit to reach the destination. (0 ≤ T ≤ 1,000,000,000)
The roads and the shortcuts are all bidirectional. There is at most one road between any two places. There is at most one shortcut between any two places. The time cost of each road or shortcut do not exceed 1,500,000 but at least 1.
Output the minimum number of short-cuts Peter has to take in one line. If it’s impossible to reach on time, print “Impossible” in a single line.