P1948 [USACO08JAN] Telephone Lines S

Years later, Benben (pinyin) grew up to become a telephone line installer. An earthquake destroyed all the city's telephone lines, and Benben is responsible for connecting the city at the epicenter. Around the city there are $n$ ($1 \le n \le 10^3$) abandoned telephone poles labeled $1$ through $n$. There are no existing lines between any pair of poles. In total, there are $p$ ($1 \le p \le 10^4$) pairs of poles that can be connected; all other pairs cannot be connected due to the earthquake. For the $i$-th connectable pair, the endpoints are $a_i, b_i$, and the distance (line length) is $l_i$ ($1 \le l_i \le 10^6$). Each pair $(a_i, b_i)$ appears at most once in the data. Pole $1$ is already connected to the national telephone network, and the entire city's network is concentrated at pole $n$. In other words, Benben only needs to find a path that connects pole $1$ to pole $n$; the other poles do not need to be connected to the network. The telecom company will support the disaster area by connecting up to $k$ ($1 \le k \le p$) pairs of poles designated by Benben for free. For any additional lines used on the chosen path, payment is required, and the total cost is determined by the longest length among those paid lines (each line connects exactly one pair of poles). If the chosen path uses at most $k$ lines, then the total cost is $0$. Please compute the minimum amount of money needed to connect the city at the epicenter.

The first line contains three integers $n, p, k$. Each of the next $p$ lines contains three integers $a_i, b_i, l_i$.

Output a single integer: the minimum total cost of the project. If it is impossible to complete, output $-1$.

Translated by ChatGPT 5