CF576D.Flights for Regular Customers

In the country there are exactly n cities numbered with positive integers from 1 to n. In each city there is an airport is located.

Also, there is the only one airline, which makes m flights. Unfortunately, to use them, you need to be a regular customer of this company, namely, you have the opportunity to enjoy flight i from city a__i to city b__i only if you have already made at least d__i flights before that.

Please note that flight i flies exactly from city a__i to city b__i. It can not be used to fly from city b__i to city a__i. An interesting fact is that there may possibly be recreational flights with a beautiful view of the sky, which begin and end in the same city.

You need to get from city 1 to city n. Unfortunately, you've never traveled by plane before. What minimum number of flights you have to perform in order to get to city n?

Note that the same flight can be used multiple times.

该国恰好有 $n$ 座城市，编号为从 $1$ 到 $n$ 的正整数。每座城市中均设有一座机场。

此外，全国仅有一家航空公司，运营 $m$ 条航线。不幸的是，要乘坐这些航班，您必须是该航空公司的常旅客：即只有在您此前已乘坐过至少 $d_i$ 次航班的前提下，才可乘坐第 $i$ 条航班（从城市 $a_i$ 飞往城市 $b_i$）。

请注意，第 $i$ 条航班严格地仅允许从城市 $a_i$ 飞往城市 $b_i$，不可反向（即不能从城市 $b_i$ 飞往城市 $a_i$）。一个有趣的现象是，可能存在起止点均为同一城市的观光航班（例如用于欣赏天空美景）。

您需要从城市 $1$ 到达城市 $n$。不幸的是，您此前从未乘坐过飞机。那么，为抵达城市 $n$，您最少需要乘坐多少次航班？

注意：同一条航班可以被重复使用多次。

The first line contains two integers, n and m (2 ≤ n ≤ 150, 1 ≤ m ≤ 150) — the number of cities in the country and the number of flights the company provides.

Next m lines contain numbers a__i, b__i, d__i (1 ≤ a__i, b__i ≤ n, 0 ≤ d__i ≤ 109), representing flight number i from city a__i to city b__i, accessible to only the clients who have made at least d__i flights.

第一行包含两个整数 $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$ 次航班的客户开放。

Print "Impossible" (without the quotes), if it is impossible to get from city 1 to city n using the airways.

But if there is at least one way, print a single integer — the minimum number of flights you need to make to get to the destination point.

如果无法通过航线从城市 1 到达城市 $n$，则输出 "Impossible"（不带引号）。

否则（即至少存在一条路径），输出一个整数 —— 到达目的地所需的最少航班次数。