You're living in the future, way beyond the singularity and the exhaustion of ipv6, and you want to plan a fastest trip between your own planet and the planet of the your favourite restaurant.

You have a map of one-directional nanobot ferry lines between the planets in your system. The map states the distance d_ij between each (connected) pair of planets i and j, but due to the rapid technical evolution of this time, you estimate the travel time from i to j is d_ij/t where t is the time at which you choose to depart from i. (It is impossible to travel at t=0).

Input

The first line contains T the number of test cases.

The first line of each test case contains integers t0, N, M where

• t0 is the time at which you start your trip. 0 ≤ t0 ≤ 10⁹
• N is the number of planets in your system, numbered 0...N-1. 0 < N ≤ 2.5*10⁵
• M is the number of connections between planets. 0 < M ≤ 2.5*10⁵

The following M lines of each test case contain integers i, j, d where

• i is the source planet. 0 ≤ i < N
• j is the destination planet. 0 ≤ j < N
• d is the distance from i to j. 0 ≤ d ≤ 10⁹

Output

The arrival time at planet N-1 when starting at planet 0 at time t0, or "Impossible" (quotes for emphasis) if there is no possible route.

Example

Input:
2
0 5 5
0 2 2
2 3 3
3 4 4
0 1 5
1 4 6
0 2 1
1 1 0

Output:
4.91760625098
Impossible