Dinner

Time limit1sMemory limit128 MB

Summary

Given a complete graph on n vertices with edge years (default 2008), find the smallest year Y such that vertices split into two parts of size at most 2n/3, one with all edges before Y, the other with all edges at or after Y.

Level: Hard8 of 10
Topics: Graph, Sorting, Union-find, Implementation
Solved: No attempts yet

Problem

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.

Input

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$ .

Output

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.

Examples2

Example 1
Input
```
6 3
1 2 1970
3 4 1980
5 6 1990
```
Expected output
```
1971
```

Example 2

Input

Expected output

Impossible