Pay2Win

Hibi recently made a new game. This game is a so-called Pay2Win game, where players must spend real money.

With development almost finished, Hibi has only the boss battle left, and has already planned the boss patterns. The boss patterns that Hibi planned are as follows.

• The boss stage is divided into $N$ zones, and the player starts at a starting position chosen by Hibi.
• The boss uses $K$ patterns, and each pattern number is a distinct positive integer at most $K$.
• The boss uses all patterns one by one in order of their numbers. Each pattern is written as $(i,j,x)$, which swaps zone $i$ and zone $j$. If the player is at zone $i$, the player moves to zone $j$, and if the player is at zone $j$, the player moves to zone $i$. The player can skip this pattern by paying $x$ won.
• The boss starts with $H$ health, and when the boss health reaches $0$, the player wins and the game ends.
• After all $K$ patterns have passed, if the player is in zone $N$, the player reduces the boss health by $1$. Otherwise, the player loses and the game ends.
• If the game has not ended, the $K$ patterns are applied again in order, and the check for whether the player is in zone $N$ repeats. The player does not return to the starting position, but skipping a pattern that was already skipped requires paying its cost again.

Hibi wants to earn as much as possible. So Hibi chooses a starting position that maximizes the minimum cost the player must pay to win. For a fair game, the player must have a way to win from the chosen starting position.

The first line contains the number of zones $N$, the number of patterns $K$, and the boss health $H$, separated by spaces. ($1\le N\le 200\,000$, $0\le K\le 200\,000$, $1\le H\le 100$)

From the second line onward, the $(p+1)$-th line contains three integers $i$, $j$, and $x$ separated by spaces, which describe the $p$-th boss pattern. ($1\le i<j\le N$, $0\le x\le 10^9$)

Print, on the first line, the minimum cost the player must pay when Hibi chooses the starting position appropriately.