405259: GYM101858 K Killua's Race

During the Hunter's Exam, you met Gon and Killua.

The hidden phase of Hunter's Exam (not shown on the anime, because it's hidden) consists of a race inside a city. The city has $$$m$$$ bidirectional roads and $$$n$$$ road intersections. All rookies have to go from intersection $$$1$$$ to intersection $$$n$$$.

You, Gon and Killua are very fast and you don't care very much about the race results, so Killua challenged you two to race under certain constraints:

• You have to take a path whose the number of roads in it is divisible by $$$3$$$.
• Gon has to take a path whose the number of roads in it minus $$$1$$$ is divisible by $$$3$$$.
• Killua to take a path whose the number of roads in it minus $$$2$$$ is divisible by $$$3$$$.

A path $$$(p_0, p_1, ..., p_n)$$$ has a total of $$$n$$$ roads in it (repeating the same road is allowed and counts for each time you walk on the roads).

The three of you are smart enough to take the shortest path under the race constraints. Also you're allowed to walk the same road or intersection more than once, but as soon as you reach the intersection $$$n$$$ you can't keep walking (it's part of the Hunter's Exam's rules).

What are the race results?

The first line of input contains two integers, $$$n$$$ and $$$m$$$ ($$$2 \le n \le 10^5$$$, $$$0 \le m \le min(n \times (n-1) / 2, 10^5)$$$) — the number of road intersections and the number of roads in the city.

The next $$$m$$$ lines contains, each, three integers, $$$u_i$$$, $$$v_i$$$ and $$$w_i$$$ ($$$1 \le u_i, v_i \le n$$$, $$$1 \le w_i \le 10^3$$$) — the road end-points and length.

It's guaranteed that there's no two roads $$$i$$$ and $$$j$$$ such that $$$(u_i, v_i) = (u_j, v_j)$$$ or $$$(u_i, v_i) = (v_j, u_j)$$$.

Print three lines, containing the order you, Gon and Killua get to the intersection $$$n$$$.

Each line must be one of the three strings: "me", "Gon" or "Killua" (without quotes).

If two or more reach the intersection $$$n$$$ at the same time, you can output them in any order.

If someone can't reach the intersection $$$n$$$ under certain constraints, it should be the last one.

If more than one can't reach the intersection $$$n$$$, both should be the last ones, in any order.

4 5
1 4 1
1 2 2
2 4 2
2 3 3
3 4 3

Gon
Killua
me

3 2
1 2 2
2 3 1

Killua
Gon
me