Magical Dungeon

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

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

The mayor told him that the monster seemed to come from the west. So he walked through a forest swept away in the west of the village and found a suspicious cave. Surprisingly, there was a deep dungeon in the cave. He got sure this cave was the lair of the monster.

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

The amount of damage he can take is indicated by hit points. He has his maximal hit points at the beginning and he goes dead if he lost all his hit points. Of course, the dead cannot move nor fight—his death means the failure of his mission. On the other hand, he can regain his hit points up to his maximal by passing healing paths. The amount he gets healed or damaged is shown in the map.

Now, he wants to fight the monster with the best possible condition. Your job is to maximize his hit points when he enters the monster’s room. Note that he must fight with the monster once he arrives there. You needn’t care how to return because he has a magic scroll to escape from a dungeon.

Input

The input consists of multiple test cases.

The first line of each test case contains two integers N (2 ≤ N ≤ 100) and M (1 ≤ M ≤ 1000). N denotes the number of rooms and M denotes the number of paths. Rooms are labeled from 0 to N−1. Each of next M lines contains three integers f_i, t_i and w_i (|w_i| ≤ 10^7), which describe a path connecting rooms. f_i and t_i indicate the rooms connected with the entrance and exit of the path, respectively. And w_i indicates the effect on Arthur’s hit points; he regains his hit points if w_i is positive; he loses them otherwise. The last line of the case contains three integers s, t and H (0 < H ≤ 10^7). s indicates the entrance room of the dungeon, t indicates the monster’s room and H indicates Arthur’s maximal hit points. You can assume that s and t are different, but f_i and t_i may be the same.

The last test case is followed by a line containing two zeroes.

Output

For each test case, print a line containing the test case number (beginning with 1) followed by the maximum possible hit points of Arthur at the monster’s room. If he cannot fight with the monster, print the case number and "GAME OVER" instead.