Minjun, Masan, and Gunwoo

With the semester over, Minjun was planning a trip down to his hometown, Masan. As always, he was about to book a bus to Masan when another way home occurred to him: look at the map himself and find the shortest route to his hometown.

Just then he got a call from his friend Gunwoo, who had gone down to his hometown first. On the way down, Gunwoo got caught up in something unknown and was left alone in a remote place. Gunwoo was asking Minjun, his only savior, for help. But to Minjun, a man of Masan, Masan came first. Minjun tried to leave for his hometown, ignoring pitiful Gunwoo, but he thought that if Gunwoo happened to be on the way home, he might as well help him.

The map is an undirected graph. The starting point is vertex 1, and Masan is vertex V. The vertices are numbered 1~V. Gunwoo is at vertex P. A path from vertex 1 to vertex P and to vertex V always exists. There are no duplicate edges and no self-loops.

Given the graph below,

In the case above, there are two shortest paths: 1→3→4→5→6 or 1→3→5→6. Among them, one shortest path includes where Gunwoo is, namely vertex 4, so in this case Minjun can help Gunwoo.

If the length of the path on which Minjun helps Gunwoo does not become longer than the length of the shortest path, Minjun will always go to help Gunwoo.

Let us help out Minjun's friendship, which he might just keep!

The first line of the input gives the number of vertices V, the number of edges $E$, and the vertex P where Gunwoo is located. (2 ≤ V ≤ 5,000, 1 ≤ E ≤ 10,000, 1 ≤ P ≤ V)

From the second line, E lines follow, each giving the information a,b,c of an edge, separated by spaces. This means the distance between vertex a and vertex b is c. (1 ≤ a,b ≤ V, 1 ≤ c ≤ 10,000)

If Gunwoo lies on the shortest path Minjun found, output "SAVE HIM"; otherwise output "GOOD BYE".