만찬

분할과 조합론에 관한 학회(NCPC)의 참가자 수가 수백 명 규모로 늘어났다. 학회가 열리는 호텔에는 큰 식당이 두 곳 있지만, 각 식당은 혼자서 전체 참가자의 최대 3분의 2까지만 수용할 수 있다. 그래서 만찬을 위해 참가자들을 두 그룹으로 나누어야 한다.

주최 측은 참가자들이 즐거워할 만한 재치 있는 규칙으로 그룹을 나누고 싶어 한다. 즉, 다음을 만족하는 연도 $Y$와 참가자들을 두 그룹으로 나누는 분할이 존재하는가?

• 첫 번째 그룹에 속한 모든 사람 쌍은 연도 $Y$ 이전에 서로 처음 만났고,
• 두 번째 그룹에 속한 모든 사람 쌍은 연도 $Y$ 당해이거나 그 이후에 서로 처음 만났다.

또한 좌석 제한 때문에, 두 그룹 중 어느 쪽도 전체 $n$명 중 $2n/3$명을 초과해서는 안 된다.

이러한 분할이 가능한 가장 작은 연도 $Y$를 구하라.

첫째 줄에 두 정수 $n$과 $c$가 주어진다. $n$은 참가자 수($4 \le n \le 400$)이고, $c$는 알려진 첫 만남의 수이다.

다음 $c$개의 줄에는 각각 세 정수 $a$, $b$, $y$ ($1 \le a < b \le n$, $1948 \le y < 2008$)가 주어지며, 이는 참가자 $a$와 $b$가 연도 $y$에 서로 처음 만났음을 뜻한다.

어떤 참가자 쌍도 목록에 두 번 이상 나타나지 않는다. 목록에 없는 모든 쌍은 바로 지금, 즉 $2008$년에 처음 만난 것으로 간주한다.

참가자들을 두 그룹으로 나누되 어느 그룹도 $2n/3$명을 초과하지 않으면서, 첫 번째 그룹의 모든 쌍은 연도 $Y$ 이전에 만났고 두 번째 그룹의 모든 쌍은 연도 $Y$ 당해이거나 그 이후에 만난, 그러한 분할이 가능한 가장 작은 연도 $Y$를 한 줄에 출력한다.

그러한 연도가 없으면 대신 Impossible을 출력한다.