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.

Input

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.

Output

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.