Магічна Темниця

Артур С. Малорі — мандрівний доблесний боєць у світі гри.

Одного разу він завітав до маленького села і залишився там на ніч. Наступного ранку до нього звернувся сільський голова, який повідомив, що селу загрожує монстр, і попросив Артура допомогти. Артур, будучи добрим, вирішив врятувати село.

Голова розповів, що монстр, ймовірно, прийшов із заходу. Тому Артур вирушив через ліс, що простягався на захід від села, і знайшов підозрілу печеру. На його здивування, у печері було глибоке підземелля. Артур був упевнений, що це лігво монстра.

На щастя, на вході він знайшов карту підземелля. Згідно з картою, монстр перебуває в глибині підземелля. У підземеллі є багато кімнат, з'єднаних шляхами. Усі шляхи односторонні і наповнені магічною силою, яка або зцілює, або завдає шкоди, коли Артур проходить шлях.

Кількість шкоди, яку він може отримати, вимірюється в очках здоров'я. Спочатку він має максимальні очки здоров'я, і якщо він втрачає всі свої очки, то помирає. Мертвий не може рухатися чи битися, а його смерть означає провал місії. З іншого боку, він може відновити свої очки здоров'я до максимальних, проходячи зцілювальні шляхи. Кількість, на яку він зцілюється або отримує шкоду, вказана на карті.

Тепер Артур хоче битися з монстром у найкращому можливому стані. Ваше завдання — максимізувати його очки здоров'я, коли він входить у кімнату з монстром. Зверніть увагу, що він повинен битися з монстром, як тільки прибуде туди. Вам не потрібно турбуватися про повернення, оскільки у нього є магічний сувій для втечі з підземелля.

Вхідні дані

Вхід складається з кількох тестових випадків.

Перша строка кожного тестового випадку містить два цілі числа N (2 ≤ N ≤ 100) та M (1 ≤ M ≤ 1000). N позначає кількість кімнат, а M позначає кількість шляхів. Кімнати позначені від 0 до N−1. Кожна з наступних M строк містить три цілі числа f_i, t_i та w_i (|w_i| ≤ 10^7), які описують шлях, що з'єднує кімнати. f_i та t_i вказують на кімнати, з'єднані входом та виходом шляху відповідно. А w_i вказує на ефект на очки здоров'я Артура; він відновлює свої очки здоров'я, якщо w_i позитивне; втрачає їх інакше. Остання строка випадку містить три цілі числа s, t та H (0 < H ≤ 10^7). s вказує на вхідну кімнату підземелля, t вказує на кімнату з монстром, а H вказує на максимальні очки здоров'я Артура. Ви можете припустити, що s та t різні, але f_i та t_i можуть бути однаковими.

Останній тестовий випадок супроводжується строкою, що містить два нулі.

Вихідні дані

Для кожного тестового випадку виведіть строку, що містить номер тестового випадку (починаючи з 1), за яким слідує максимальна можлива кількість очок здоров'я Артура в кімнаті з монстром. Якщо він не може битися з монстром, виведіть номер випадку та "GAME OVER".