SP16272 NANO - Nanoworld

在未来的某个时间，你需要从你居住的星球前往你最爱的餐馆所在的星球。星际旅行的科技已经相当发达，你需要找到最快的行程。 你拥有一张星际地图，标注了各个星球之间的单向纳米机器人渡轮线路。在这张地图上，每对相连星球 **i** 和 **j** 之间的距离表示为 **d $ _{ij} $**。由于科技的飞速发展，你估计从 **i** 行驶到 **j** 的时间为 **d $ _{ij} $ / t**，其中 **t** 是你从 **i** 出发的时间。（注意：不能从 t=0 出发）。

第一行输入一个整数 **T**，表示待处理的测试用例的数量。 每个测试用例的第一行包含三个整数 **t0**、**N** 和 **M**，分别表示： - **t0** 为你开始旅行的时间。0 ≤ **t0** ≤ 10 $ ^{9} $ - **N** 是星球的数量，编号从 0 到 N-1。0 < **N** ≤ 2.5\*10 $ ^{5} $ - **M** 是星球之间线路的数量。0 < **M** ≤ 2.5\*10 $ ^{5} $ 接下来 **M** 行，每行包含三个整数 **i**、**j** 和 **d**，表示： - **i** 为出发星球。0 ≤ **i** < **N** - **j** 为目标星球。0 ≤ **j** < **N** - **d** 是从 **i** 到 **j** 的距离。0 ≤ **d** ≤ 10 $ ^{9} $

输出从星球 0 在时间 **t0** 出发到达星球 **N**-1 的时间。如果没有可行的路线可达目标星球，则输出「Impossible」。 **本翻译由 AI 自动生成**