마법의 던전

아서 C. 말로리는 (게임 세계에서) 떠돌아다니는 용감한 전사다.

어느 날 그는 작은 마을을 방문해 하룻밤을 묵었다. 다음 날 아침 마을 촌장이 그를 찾아왔다. 촌장은 괴물이 마을을 위협하고 있으니 처치해 달라고 부탁했다. 그는 마음이 넓은 사람이라 마을을 구하는 일을 돕기로 했다.

촌장은 괴물이 서쪽에서 온 것 같다고 했다. 그래서 그는 마을 서쪽 숲을 지나 수상한 동굴을 찾아냈다. 놀랍게도 동굴 안에는 깊은 던전이 있었다. 그는 이 동굴이 괴물의 소굴이라고 확신했다.

다행히 입구에서 던전 지도를 받았다. 지도에 따르면 괴물은 던전 깊숙한 곳에 있다. 던전에는 길로 이어진 방이 많다. 모든 길은 일방통행이며 마법의 힘이 가득하다. 마법의 힘은 그가 길을 지날 때 체력을 회복시키거나 피해를 준다.

그가 견딜 수 있는 피해의 양은 체력으로 나타낸다. 그는 처음에 최대 체력 상태로 출발하며, 체력을 모두 잃으면 죽는다. 죽은 사람은 움직이거나 싸울 수 없으므로, 죽으면 임무는 실패다. 반면 회복 길을 지나면 최대 체력까지 체력을 회복할 수 있다. 회복하거나 피해를 입는 양은 지도에 표시되어 있다.

이제 그는 최상의 상태로 괴물과 싸우려 한다. 당신의 일은 그가 괴물의 방에 들어갈 때 체력을 최대한 높이는 것이다. 괴물의 방에 도착하면 반드시 바로 싸워야 한다. 돌아오는 길은 신경 쓰지 않아도 된다. 던전을 빠져나갈 마법 두루마리가 그에게 있기 때문이다.

입력은 여러 개의 테스트 케이스로 이루어진다.

각 테스트 케이스의 첫 줄에는 두 정수 $N$ ($2 \le N \le 100$)과 $M$ ($1 \le M \le 1000$)이 주어진다. $N$은 방의 개수, $M$은 길의 개수다. 방은 $0$부터 $N-1$까지 번호가 붙어 있다. 이어지는 $M$개의 줄에는 정수 $f_i$, $t_i$, $w_i$ ($|w_i| \le 10^7$)가 주어진다. 이는 방 $f_i$에서 방 $t_i$로 가는 길을 뜻한다. $w_i$는 아서의 체력에 주는 영향이다. 양수이면 체력을 회복하고, 음수이면 체력을 잃는다. 테스트 케이스의 마지막 줄에는 세 정수 $s$, $t$, $H$ ($0 < H \le 10^7$)가 주어진다. $s$는 던전의 입구 방, $t$는 괴물의 방, $H$는 아서의 최대 체력이다. $s$와 $t$는 서로 다르지만, $f_i$와 $t_i$는 같을 수 있다.

입력의 마지막은 0 두 개가 한 줄에 주어지는 것으로 끝난다.

각 테스트 케이스마다 테스트 케이스 번호(1부터 시작)와, 아서가 괴물의 방에 들어갈 때 가질 수 있는 최대 체력을 한 줄에 출력한다. 괴물과 싸울 수 없으면 테스트 케이스 번호와 "GAME OVER"를 출력한다.