Codeforces Round 319 (Div. 1) |
---|

Finished |

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

dp

matrices

*2700

No tag edit access

The problem statement has recently been changed. View the changes.

×
D. Flights for Regular Customers

time limit per test

4 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputIn 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.

Examples

Input

3 2

1 2 0

2 3 1

Output

2

Input

2 1

1 2 100500

Output

Impossible

Input

3 3

2 1 0

2 3 6

1 2 0

Output

8

Codeforces (c) Copyright 2010-2023 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Jun/04/2023 03:05:39 (j2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|