NANO  Nanoworld
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 onedirectional 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^{9}
 N is the number of planets in your system, numbered 0...N1. 0 < N ≤ 2.5*10^{5}
 M is the number of connections between planets. 0 < M ≤ 2.5*10^{5}
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^{9}
Output
The arrival time at planet N1 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
hide comments
Antonio Roberto Paoli:
20181117 02:55:56
If i=0 time is given, so I can't estimate it. In the first test case t0=0, but t=0 is not accepted because is impossible. The second paragraph need to be rewrite to make it clear, I think! 

Antonio Roberto Paoli:
20181116 21:41:35
Thomas, could you please better explain dij/t? dist/time is velocity, so, time <> dist/time. Is this an interactive problem? Last edit: 20181117 02:43:43 

Thomas Dybdahl Ahle:
20171216 23:58:57
It uses the standard Spoj judge for FP with 10^2 absolute error. 

ppm:
20171017 18:43:34
What's the expected output precision? 
Added by:  Thomas Dybdahl Ahle 
Date:  20131007 
Time limit:  1s5s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 