Flights for Regular Customers

题意翻译

- 给定一张 $n$ 个点 $m$ 条边的有向图。 - 一开始你在 $1$ 号节点，你要走到 $n$ 号节点去。 - 只有当你已经走过了至少 $d_i$ 条边时，你才能走第 $i$ 条边。 - 问最少要走多少条边，或判断无法到达。 - $n,m \le 150$，$d_i \le 10^9$。

题目描述

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.

输入输出格式

输入格式

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}<=10^{9} $ ), 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.

输出格式

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

3 2
1 2 0
2 3 1

输出样例 #1

2

输入样例 #2

2 1
1 2 100500

输出样例 #2

Impossible

输入样例 #3

3 3
2 1 0
2 3 6
1 2 0

输出样例 #3

8