You are given an undirected graph with n nodes and m weighted edges. The weight of the edge w connecting two nodes u and v denotes the cost of going from u to v or vice versa. You need to go from starting node s to destination node t within total cost c with a positive energy level left.

At the beginning of the journey, you have an initial energy level. While moving from one node to an adjacent node, the energy level decreases by 1. If your energy level becomes 0, you must back-jump to any previously visited node (not the current node) with cost d. Note that, even if you reach the destination node with energy level 0, you have to back-jump. You only finish the journey if you reach the destination node t with a positive energy level. Moreover, you can also back-jump from your current node even if you still have some energy. After any back-jump, you regain all the lost energies and your energy becomes the initial value again.

See the given figure for clarity (directed edges are used only to demonstrate the path). You started with initial energy level 3 from node 2. After reaching node 1, your energy level became 2. After reaching node 4, your energy level became 1, and after reaching node 6, your energy level became 0. So, you have to jump back. Now for a back-jump, you had three options: node 2, node 1 and node 4. So, if you jump back to any of these three nodes (in the figure, it is node 1), your energy level will become 3 again.

You need to find the minimum initial energy level required to go from starting node s to destination node t with total cost not exceeding c or determine if it's impossible to do so.

The first line contains an integer T (1 ≤ T ≤ 10) denoting the number of test cases.

The first line of each test case contains six integers n, m, s, t, c, d (2 ≤ n ≤ 500, 1 ≤ m ≤ 500, 1 ≤ s, t ≤ n, s ≠ t, 1 ≤ c, d ≤ 10⁹). Each of the next m lines contains three integers u, v, w (1 ≤ u, v ≤ n, u ≠ v, 1 ≤ w ≤ 10⁹) denoting an edge between node u and v with cost w.

For each case, print Case t: x, where t is the test case number and x is an integer denoting the minimum energy or a string Impossible if not possible.