Dinner

The number of participants at the Nordic Conference on Partitions and Combinatorics (NCPC) has grown into the hundreds. The conference is held at a hotel with two large dining halls, but each hall on its own can seat at most two thirds of the participants, so for the conference dinner the participants must be divided into two groups.

The organizers want the division to follow a clever rule they can announce for everyone's amusement. That is, does there exist a year $Y$ and a division of the participants into two parts such that

• every pair of people in the first part met each other for the first time before year $Y$, and
• every pair of people in the second part met each other for the first time in or after year $Y$?

In addition, because of the seating limit, neither part may contain more than $2n/3$ of the $n$ participants.

Find the smallest year $Y$ for which such a division exists.

The first line contains two integers $n$ and $c$: the number of participants ($4 \le n \le 400$) and the number of known first encounters.

Each of the next $c$ lines contains three integers $a$, $b$, and $y$ ($1 \le a < b \le n$, $1948 \le y < 2008$), meaning that participants $a$ and $b$ met each other for the first time in year $y$.

No pair of participants appears more than once. Every pair of participants that is not listed is assumed to have met for the first time only now, in the year $2008$.

Print a single line with the smallest year $Y$ for which the participants can be divided into two parts, neither containing more than $2n/3$ people, such that every pair in the first part met before year $Y$ and every pair in the second part met in or after year $Y$.

If no such year exists, print Impossible instead.