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