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 one-directional nanobot ferry lines between the planets in your system. The map states the distance dij 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 dij/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 ≤ 109
  • N is the number of planets in your system, numbered 0...N-1. 0 < N ≤ 2.5*105
  • M is the number of connections between planets. 0 < M ≤ 2.5*105

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 ≤ 109

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

Added by:Thomas Dybdahl Ahle
Date:2013-10-07
Time limit:1s-5s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64

hide comments
2018-11-17 02:55:56 Antonio Roberto Paoli
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!
2018-11-16 21:41:35 Antonio Roberto Paoli
Thomas, could you please better explain dij/t? dist/time is velocity, so, time <> dist/time. Is this an interactive problem?

Last edit: 2018-11-17 02:43:43
2017-12-16 23:58:57 Thomas Dybdahl Ahle
It uses the standard Spoj judge for FP with 10^-2 absolute error.
2017-10-17 18:43:34 ppm
What's the expected output precision?
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.