# 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
``````