H. Higgs
time limit per test
2 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

Risa is the greatest thief in the GianParme Galaxy, and she is preparing for her biggest heist yet. The target is on planet Amorim, named after its fearless leader Matheus Amorim, who ruled the planet for many years until his tragic passing.

Risa's goal is to steal the planet's greatest relic, the crown that Matheus wore during his reign. The artifact is stored in a museum on planet Amorim. The first step of her plan is figuring out how to reach this planet.

The GianParme Galaxy can be modeled by $$$N$$$ planets numbered from $$$1$$$ to $$$N$$$ and $$$M$$$ connections between them. Each connection is represented by two planets $$$(u, v)$$$ and a "Higgs level" $$$h$$$. The connections are designed such that it's possible to travel from any planet to any other planet using the galaxy's connections.

The Higgs level is a form of security in the galaxy; all residents of GianParme have their own Higgs level, and to use a connection between two planets, their Higgs level must be greater than or equal to the Higgs level of that connection.

Risa is currently on planet number $$$1$$$, and planet Amorim is planet number $$$N$$$. Since Risa is a well-known thief, her Higgs level is $$$0$$$, and to complete her journey to planet Amorim, she has two options:

  • Bribe the guard of a connection to use it regardless of her Higgs level.
  • Forge her identity to have any Higgs level she desires.

However, forging an identity is a very difficult task, so she needs to know: What is the minimal Higgs level she must forge in order to complete her journey to planet Amorim, knowing she has enough money to bribe $$$K$$$ guards?

Input

The first line of the input consists of three integers $$$N$$$ $$$(2 \le N \le 3 \cdot 10^5)$$$, $$$M$$$ $$$(1 \le M \le 3 \cdot 10^5)$$$, and $$$K$$$ $$$(0 \le K \le M)$$$, representing the number of planets, the number of connections, and the number of guards Risa can bribe, respectively.

The next $$$M$$$ lines each contain three integers $$$u$$$, $$$v$$$ $$$(1 \le u, v \le N)$$$ and $$$h$$$ $$$(1 \le h \le 10^9)$$$, indicating that there is a connection between planets $$$u$$$ and $$$v$$$ with Higgs level $$$h$$$.

Output

The output must contain a single integer, the minimal Higgs level Risa needs to forge to complete her journey.

Examples
Input
4 4 1
1 2 3
2 4 4
1 3 3
3 4 1
Output
1
Input
6 6 2
1 2 1
2 3 3
3 4 10
4 6 4
3 5 2
5 6 4
Output
2
Input
5 6 2
1 2 3
1 3 2
2 3 1
3 4 5
4 5 3
2 4 4
Output
2