Telephone Lines

Farmer John wants to set up a telephone line at his farm. Unfortunately, the phone company is uncooperative, so he must pay for some of the cables needed to connect his farm to the telephone system.

There are $n$ forlorn telephone poles, conveniently numbered from $1$ to $n$, scattered around Farmer John's property; no cables currently connect any of them. A total of $p$ pairs of poles can be connected by a cable; the remaining pairs are too far apart.

The $i$-th cable can connect two distinct poles a_i and b_i with a length of l_i~(1 \le l_i \le 10^6) units. Each pair {a_i,b_i} appears at most once in the input.

Pole $1$ is already connected to the telephone system, while pole $n$ is located at the farm. Poles $1$ and $n$ must be connected by a path of cables; the remaining poles may or may not be used.

The phone company is willing to provide Farmer John with $k$ cable lengths for free. Beyond those $k$ free cables, Farmer John must pay a price equal to the length of the longest remaining cable he needs to use, or $0$ if no additional cables are required.

Determine the minimum amount Farmer John must pay.