558 - Wormholes

西元2163年，人類發現蟲洞，蟲洞是一條時空隧道，可以穿梭於星系間的時空，它有幾個特點：

• 蟲洞是單向的。
• 蟲洞內的移動時間可被忽略。
• 蟲洞有兩個端點，分別處在兩個不同的星系。
• 一個星系可能會有多條蟲洞的端點。
• 基於某種不明的原因，由我們地球所處的星系出發，一定可以藉由一或多條蟲洞到達其他任一星系。
• 由A星系到B星系的蟲洞最多只有一條。
• 不會有起點與終點皆在同一星系的蟲洞。

蟲洞的兩個端點間會有時差，例如，某條蟲洞可以讓人穿越到15年後的未來，而另一條蟲洞可以讓人回到42年前的過去。

有一位住在地球上的天才物理學家，她想藉由蟲洞旅行回到宇宙創始的時候，親自到那個時空研究大爆炸理論(Big Bang)。她想找出是否有一條循環路徑可以讓她回到無止盡的過去，帶她回到宇宙創始之際。請你寫一個程式判斷這樣的循環是否存在。

Input

輸入的第一列有一個整數 c 表示測試資料的組數。每組測試資料的第一列有兩個整數 n 與 m，分別表示星系總數n(1 <= n <= 1000)與蟲洞總數m(0 <= m <= 2000)。星系的編號由 0 開始到 n-1 結束(以編號 0 的星系為出發點)，接下來有 m 列表示蟲洞的資料，每列有三個整數 x, y, t，分別表示由 x 星系到 y 星系的蟲洞能讓人旅行到 t 年後的未來(-1000 <= t <= 1000)。

Output

輸出共有 c 列，每列表示每組測試資料的結果，若可以找到無止盡回到過去的循環請輸出"possible"，若不行請輸出"not possible"。

Sample Input 

2
3 3
0 1 1000
1 2 15
2 1 -42
4 4
0 1 10
1 2 20
2 3 30
3 0 -60

Sample Output 

possible
not possible

---

原文出處