409815: GYM103797 B Bus Bet

Cosenza always goes to his Middle School Internship (MSI) in his brand new red Ferrari (pandas are color blind). Unfortunately, General Macário visited the school where Cosenza does his MSI and Cosenza got caught in the $$$5$$$ Km Rule! It states: "It's prohibited to have a better car than a general in a $$$5$$$ Km radius", so his Ferrari got towed. Now he has to take the bus home.

His android arch-enemy, D8, is mocking him for this situation, even though he also has to take the bus to go home. Infuriated, Cosenza decides to make a bet to shut D8 up. He bets that, for each bus he has to take while going home, he's able to complete one entire codeforces contest just in the time between getting on the bus and getting out of it. If he takes $$$X$$$ buses to get home, he would have to finish $$$X$$$ contests, one in each bus, and complete each one in the time he spent inside each bus.

The bus routes in this city are such that each route connects only two bus stops, in both directions. Also, the buses always take exactly the same amount of time on the same route, in both directions, and everyone is kicked out of the bus at each stop as soon as it arrives.

D8 likes bets, but he likes even more to win them, so first he asks for your help to see how fast does Cosenza have to be to win the bet. If the wager is accepted, Cosenza can solely go from one station to another using buses. D8 knows that Cosenza may take a longer route home just to win this bet, as long as it's not too long. He will not walk between bus stops even if it means losing his bet. Given the bus routes, can you find the fastest Cosenza has to be in the contests in order to win the bet? In other words, given all possible routes home, find the one with the longest smallest bus section. Notice that given these constraints, it may be impossible for Cosenza to get home.

The first line of the input consists of three integers, $$$N$$$, $$$M$$$ and $$$T$$$ ($$$1 < N, M \leq 5 \times 10^5$$$ and $$$0 < T \leq 10^8$$$) — the number of bus stops, the number of bus routes, and the longest Cosenza accepts to spend going home, respectively. Consider the worst case scenario, in which there's always the exact bus Cosenza wants waiting for him at the bus stop.

Each of the next $$$M$$$ lines consists of three integers, $$$u$$$, $$$v$$$ and $$$t$$$ ($$$1 \leq u < v \leq N$$$ and $$$1 \leq t \leq 5 \times 10^5$$$) — the stops this route connects and the time it takes from one stop to the other.

A single integer, the answer to D8's question when Cosenza's MSI is at bus stop $$$1$$$ and Cosenza's home is at bus stop $$$N$$$. If it's impossible for Cosenza to get home by bus, print "He's taking an uber.".

2 2 100
1 2 1
1 2 10

10

2 2 5
1 2 10
1 2 20

He is taking an uber.

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

2