CF576D Flights for Regular Customers

在一个国家里，有 $n$ 个城市，编号为 $1$ 到 $n$ 的正整数。每个城市里都有一个机场。 此外，只有一家航空公司运营 $m$ 条航线。不幸的是，想要乘坐这些航班，你必须是该公司的常旅客 —— 具体来说，只有在你已经至少乘坐过 $d_{i}$ 次航班后，才能乘坐第 $i$ 条航班，该航班从城市 $a_{i}$ 出发，飞往城市 $b_{i}$。 请注意，第 $i$ 条航班只能从 $a_{i}$ 城市飞往 $b_{i}$ 城市，不能反向使用。同样地，可能存在观光航班，即航班起点和终点为同一城市。 你现在需要从城市 $1$ 出发，前往城市 $n$。遗憾的是，你此前没有任何乘机经历。请问，最少需要乘坐多少次航班才能到达城市 $n$？ 注意：同一条航班可以多次乘坐。

第一行包含两个整数 $n$ 和 $m$（$2 \leq n \leq 150$，$1 \leq m \leq 150$），分别表示国家中的城市数与航空公司提供的航班数。 接下来的 $m$ 行，每行包含三个整数 $a_{i}$、$b_{i}$、$d_{i}$（$1 \leq a_{i}, b_{i} \leq n$，$0 \leq d_{i} \leq 10^{9}$），表示第 $i$ 条航班从城市 $a_{i}$ 飞往城市 $b_{i}$，且只有已经乘坐过至少 $d_{i}$ 次航班的客户才能乘坐。

如果无法通过航空航线从城市 $1$ 到达城市 $n$，输出 “Impossible”。 如果存在至少一种方式到达城市 $n$，则输出一个整数，即到达目的地所需的最小航班次数。

由 ChatGPT 5 翻译