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 ai, bi, di (1 ≤ ai, bi ≤ n, 0 ≤ di ≤ 109), representing flight number i from city ai to city bi, accessible to only the clients who have made at least di 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.