Magical Dungeon

Arthur C. Malory is a wandering valiant fighter (in a game world).

One day, he visited a small village and stayed overnight. The next morning, the village mayor called on him. The mayor said a monster threatened the village and asked him to defeat it. He was so kind that he decided to help save the village.

The mayor said the monster seemed to come from the west. So he walked through a forest to the west of the village and found a suspicious cave. Surprisingly, there was a deep dungeon inside. He was sure this cave was the monster's lair.

Fortunately, at the entrance, he got a map of the dungeon. According to the map, the monster dwells deep in the dungeon. The dungeon has many rooms connected by paths. All paths are one-way and filled with magical power. The magic heals or damages him when he passes a path.

The amount of damage he can take is indicated by his hit points. He starts with his maximal hit points, and he dies if he loses all of them. The dead cannot move or fight, so death means the mission fails. On the other hand, he can regain hit points up to his maximum by passing healing paths. The amount healed or damaged is shown on the map.

Now he wants to fight the monster in the best possible condition. Your job is to maximize his hit points when he enters the monster's room. He must fight the monster as soon as he arrives there. You do not need to worry about the way back, because he has a magic scroll that lets him escape from the dungeon.

The input consists of multiple test cases.

The first line of each test case contains two integers $N$ ($2 \le N \le 100$) and $M$ ($1 \le M \le 1000$). $N$ is the number of rooms and $M$ is the number of paths. Rooms are labeled from $0$ to $N-1$. Each of the next $M$ lines contains three integers $f_i$, $t_i$, and $w_i$ ($|w_i| \le 10^7$). These describe a path from room $f_i$ to room $t_i$. $w_i$ is the effect on Arthur's hit points: he regains hit points if $w_i$ is positive, and loses them otherwise. The last line of the case contains three integers $s$, $t$, and $H$ ($0 < H \le 10^7$). $s$ is the entrance room of the dungeon, $t$ is the monster's room, and $H$ is Arthur's maximal hit points. You can assume $s$ and $t$ are different, but $f_i$ and $t_i$ may be the same.

The input ends with a line containing two zeroes.

For each test case, print a line containing the test case number (starting from 1) and the maximum hit points Arthur can have when he enters the monster's room. If he cannot fight the monster, print the case number and "GAME OVER" instead.