The Mountain of Gold?

Old stories put rich gold deposits on Gunung Ledang in Malaysia, and they drew traders from as far as Greece and China. In the 14th century the Chinese seafarers who sailed the Straits of Melaka called it Kim Sua, the golden mountain. The name Gunung Ledang, given during the Majapahit empire, means the mountain seen from afar.

Legend says the princess of Gunung Ledang travelled back to the time when the earth was made and hid a huge amount of gold in the mountain. She could turn any pool she bathed in into a portal that joins two points in space and time. A historian later found many such pools near mountains around the world and named them Ledang Pools.

A Ledang Pool has these properties.

• One pool is a one way portal between two different mountains.
• Travelling through a pool takes no time.
• A mountain may hold the end points of several pools.
• Starting from Ledang Mountain, a sequence of pools reaches every mountain.
• No pool has both of its end points on the same mountain.
• Each pool has a fixed time difference between its end points. Travelling through one pool may drop the traveller 42 years in the past at the other end.

No gold is on Ledang Mountain today, so the historian believes it is hidden on Ledang Mountain in the past. He wants to start from Ledang Mountain in the present, hop through two or more pools, and arrive back at Ledang Mountain at a moment strictly before he left. How far in the past he lands does not matter. Decide whether such a trip exists.

The first line contains the number of test cases $T$.

The first line of each test case contains the number of mountains that hold a pool end point, $N$, and the number of pools, $M$. The mountains are numbered from $0$ to $N-1$, and mountain $0$ is Ledang Mountain in Malaysia.

Each of the next $M$ lines contains three integers $A$, $B$, $C$ describing one pool. Entering that pool on mountain $A$ puts the traveller on mountain $B$, $C$ years later. A positive $C$ means the future and a negative $C$ means the past.

For each test case, print one line in the form Case #X: Y. $X$ is the test case number, counted from 1. $Y$ is possible if the historian can reach Ledang Mountain in the past, and not possible otherwise.

• $1 \le T \le 20$
• $1 \le N \le 1000$
• $0 \le M \le 2000$
• $0 \le A < N$, $0 \le B < N$, $A \ne B$
• $-1000 \le C \le 1000$
• Every mountain is reachable from mountain $0$.
• Several pools may join the same pair of mountains in the same direction.