题目描述

你是否遇到过这样的情况：你迎面走向另一个人，为了避让向左侧迈了一步，却发现对方也做出了相同的动作，于是两个人尴尬地左右摇摆，始终无法顺利通过？最近，一篇发表于“希腊商业与采购会议”的论文指出，这个问题在古希腊时期可能就已经十分常见。

当时共有 $n$ 支商队，它们偶尔会沿相反方向穿过温泉关。两支商队相遇时，双方会同时选择向山崖侧或海侧避让。

• 如果两支商队选择了不同的方向，它们就能安全通过；
• 如果选择了相同的方向，它们会再次同时选择，直到某一次选择不同为止。

商队无法从远处辨认另一支商队，因此每支商队都会按照一个确定性的策略依次决定每次向哪一侧避让。

由于向海侧避让危险得多，我们将一个策略的风险值定义为该策略中选择向海侧避让的总次数。

例如，一支商队的策略可能依次为：

山崖侧、海侧、海侧、山崖侧、海侧，之后永远选择山崖侧。

该策略的风险值为 $3$。

所有商队来到德尔斐神谕处，希望得到应当采用何种策略的建议。然而神谕并没有直接给出策略，而是说出了 $m$ 条预言。每条预言形如：

当商队 $u$ 和商队 $v$ 相遇时，它们会恰好连续 $t$ 次选择相同的方向，并在第 $t+1$ 次选择不同的方向，从而安全通过。

真实的策略早已失传。你希望构造一组满足全部预言的策略，并使所有商队策略的风险值之和最小。

输入格式

第一行包含两个整数 $n,m$（$2\le n\le 2\cdot 10^5$，$1\le m\le 4\cdot 10^5$），分别表示商队数量和预言数量。

接下来 $m$ 行，每行包含三个整数 $u,v,t$（$1\le u,v\le n$，$u\ne v$，$0\le t\le 10^9$），表示商队 $u$ 与商队 $v$ 会连续 $t$ 次选择相同方向，然后在下一次选择不同方向。

保证每一对商队至多在输入中出现一次。

输出格式

如果不存在满足全部预言的策略集合，输出：

impossible

否则，先输出：

possible

然后输出一个整数，表示所有满足预言的策略集合中，最小可能的总风险值。

样例 1

输入

5 3
1 2 2
1 3 0
4 5 2

输出

possible
3

说明

可以选择如下策略：

• 商队 $1$ 永远选择山崖侧，风险值为 $0$；
• 商队 $2$ 依次选择山崖侧、山崖侧、海侧，之后永远选择山崖侧，风险值为 $1$；
• 商队 $3$ 第一次选择海侧，之后永远选择山崖侧，风险值为 $1$；
• 商队 $4$ 永远选择山崖侧，风险值为 $0$；
• 商队 $5$ 依次选择山崖侧、山崖侧、海侧，之后永远选择山崖侧，风险值为 $1$。

这些策略满足全部预言，总风险值为 $3$，且这是最小值。

样例 2

输入

4 3
1 2 3
2 4 4
1 4 2

输出

impossible