Description

Original source: USACO 2008 Jan. Silver

In the suburbs, there are $N$ communication base stations and $P$ bidirectional cables, where the $i$-th cable connects base stations $A_i$ and $B_i$. Notably, base station $1$ is the main station of the communication company, and base station $N$ is located on a farm. Now, the farm owner wishes to upgrade the communication lines, where upgrading the $i$-th cable costs $L_i$.

The telephone company is running a promotional offer. The farm owner can specify a path from base station $1$ to base station $N$ and designate up to $K$ cables on this path to be upgraded for free by the telephone company. The farm owner only needs to pay for the cost of the most expensive remaining cable on the path after the free upgrades. Determine the minimum amount of money required to complete the upgrade.

In one sentence $\ \$ On a weighted undirected graph, find a path from node $1$ to node $N$ such that the $(K + 1)$-th largest edge weight on the path is as small as possible.

Input Format

The first line contains three integers $N, P, K$.

The next $P$ lines each contain three integers $A_i, B_i, L_i$.

Output Format

If there is no path from $1$ to $N$, output -1. Otherwise, output the minimum required cost.

Sample 1

5 7 1
1 2 5
3 1 4
2 4 8
3 2 3
5 2 9
3 4 7
4 5 6

4

Constraints & Hints

$0 \le K < N \le 1000, 1 \le P\le 2000$