I. Транспортировка: только время

Как классная задача I, но кружек ровно $k$ — их количество дано во входных данных. Найдите наименьшее время доставки.

Бинарный поиск здесь не нужен вовсе: вес грузовика известен, дороги отфильтрованы, дальше — одна Дейкстра.

Задача полезна как проверка проверки: именно это и делается внутри бинарного поиска классной задачи. Если она не проходит, ошибка не в поиске.

Первая строка содержит числа $n$ ($1 \le n \le 500$), $m$ ($0 \le m \le 10^5$) и $k$ ($0 \le k \le 10^7$).

Далее идут $m$ строк: два пункта, время проезда (не больше 1440) и ограничение на вес в граммах (не больше $10^9$).

Одно число — наименьшее время в минутах или $-1$, если проехать нельзя. Ограничение в 24 часа здесь не проверяется.