Problem Statement

You are given a simple undirected graph with $N$ vertices and $M$ edges. The graph as a whole is guaranteed to be connected.

Edge $i$ ($1 \le i \le M$) connects vertices $u_i$ and $v_i$ and has a parameter $c_i$.

Seneko has a bag, which initially contains $K$ cards with $0$ written on them.

Seneko starts at vertex $1$ and travels on the graph.

When Seneko traverses edge $i$, she puts $1$ card with $c_i$ written on it into the bag. (If she traverses the same edge multiple times, she puts in $1$ card each time.)

Some time after starting the journey, Seneko was at vertex $N$. At this point, find the minimum possible value of the number written on the card that comes $K$-th when the cards in the bag are arranged in descending order.

Note that Seneko moves only between $2$ vertices connected by an edge, and she may use the same edge $2$ or more times.

Input

$N\ M\ K$
$u_1\ v_1\ c_1$
$u_2\ v_2\ c_2$
$\vdots$
$u_M\ v_M\ c_M$

• All inputs are integers.
• The given graph is a connected simple undirected graph.
• $2 \le N \le 2 \times 10^5$
• $N-1 \le M \le \mathrm{min}\left(2 \times 10^5, \frac{N (N - 1)} {2}\right)$
• $1 \le K \le 2 \times 10^5$
• $1 \le u_i < v_i \le N$
• If $i \neq j $, then $(u_i,v_i) \neq (u_j,v_j)$
• $1 \le c_i \le 2 \times 10^5$

Output

Output the answer on one line. End the output with a newline.

Sample

2 1 1
1 2 100

100

2 1 2
1 2 100

0

4 4 2
1 2 50
2 4 50
1 3 100
3 4 1

1