問題文

$N$ 頂点 $M$ 辺の単純無向グラフが与えられます。グラフ全体は連結であることが保証されます。

辺 $i$ ($1 \le i \le M$) は、頂点 $u_i$ と $v_i$ を結んでおり、パラメータ $c_i$ を持ちます。

せねこさんは袋を持っており、その中には最初 $0$ が書かれたカード $K$ 枚が入っています。

せねこさんは、頂点 $1$ からスタートしてグラフ上を旅します。

せねこさんは辺 $i$ を通った時、 $c_i$ が書かれたカードを袋の中に $1$ 枚入れます。(同一の辺を複数回通った場合、その度にカードを $1$ 枚入れます)

旅を始めてからしばらくして、せねこさんは頂点 $N$ にいました。 この時、袋の中に入っているカードを降順に並べた場合に $K$ 番目にくるカードに書かれている数として考えられる最小のものを求めてください。

ただし、せねこさんは辺で接続された $2$ 頂点間のみを移動し、 $2$ 回以上同じ辺を利用することもあることに注意してください。

入力

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

• 入力は全て整数
• 与えられるグラフは連結な単純無向グラフ
• $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$
• $i \neq j $ であれば $(u_i,v_i) \neq (u_j,v_j)$
• $1 \le c_i \le 2 \times 10^5$

出力

答えを1行に出力してください。最後に改行してください。

サンプル

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