虫洞

Grade 100 Open Time Wednesday, 17 June 2020, 8:45 PM
Discount 0.8 Time Discount Wednesday, 17 June 2020, 8:45 PM
Allow late Yes Close Time Wednesday, 17 June 2020, 8:45 PM
Input file hole.in Output file hole.out

 【题目描述】虫洞(hole)UVA 558

虫洞是时空中连接两个星系的子空间通道。虫洞有一些特别的性质:

(1)虫洞是单向通道。

(2)通过虫洞的用时可忽略。

(3)虫洞有两个口,每个口都在星系里。

(4)从太阳系出发总是能通过一系列的虫洞到达任何其他星系。

(5)对于任何一对星系,其间每个方向上至多有一个虫洞。

(6)没有虫洞两个口都在一个星系里。

所有虫洞都有自己恒定的时差,例如,某个虫洞可以让人到未来15年后,另一个虫洞可能让人回到42年前。   

一个科学家想通过虫洞研究宇宙诞生时的大爆炸,她准备通过虫洞实现,她希望到达一个虫洞环(虫洞环是一系列首尾相连的虫洞)并在环上走一圈后能让她回到过去,如此一来,她只要在环上通行足够多次,就能回到宇宙的开端,亲眼看到大爆炸。写一个程序帮助她找到这样的虫洞环。

【输入格式】

第一行为星系个数n(1≤n≤1 000)和虫洞个数m(1≤m≤2 000)。星系编号从0(太阳系)到n-1。下面m行描述m个虫洞,格式均为x,y,t。其中x,y是虫洞两个口位于的星系编号,t(-1 000≤t≤1 000)为虫洞的时差。

【输出格式】

如找到合适的虫洞环,输出Possible,否则输出Not possible。

【输入样例1】

3 3

0 1 1000

1 2 15

2 1 -42

【输出样例1】

Possible

【输入样例2】

4 4

0 1 10

1 2 20

2 3 30

3 0 -60

【输出样例2】

Not possible