Wormholes#1108
In the year 2163, wormholes were discovered. A wormhole is a tunnel through space and time connecting two star systems. Wormholes have the following properties:
Wormholes are one-way only.
The time to travel through any wormhole is zero.
A wormhole has two endings, each located in a star system.
A star system may contain several wormhole endpoints within its boundaries.
For some unknown reason, starting from our solar system, it is always possible to reach any other star system by following some sequence of wormholes (perhaps because Earth is the center of the universe).
Between any pair of star systems, there is at most one wormhole in each direction.
Both ends of a wormhole cannot be located in the same star system.
Each wormhole moves the traveler a certain constant number of years forward or backward. For example, one wormhole may move the traveler 15 years into the future, another 42 years into the past.
A renowned physicist living on Earth wants to use wormholes to study the Big Bang theory. Since a warp drive has not yet been invented, it is not possible to travel directly between star systems. However, this can be done using wormholes.
The scientist wants to find a cycle of wormholes that will transport her into the past. By traveling along this cycle several times, she can reach the time of the Big Bang and witness it with her own eyes. Write a program to determine if such a cycle exists.
The first line contains the number of star systems (1 \leq n \leq 1000) and the number of wormholes (0 \leq m \leq 2000). The star systems are numbered from (our solar system) to n - 1. Each wormhole is described on a separate line and contains three integers , , and . These numbers indicate that there is a wormhole from star system to star system , and traversing it changes the time by (-1000 \leq t \leq 1000) years.
Output one line: "possible" if it is possible to go back in time infinitely using the given set of systems and wormholes, or "not possible" otherwise.
Example 1
Example 2