SP16272 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 **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).

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...N-1. 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} $

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.